Very Sparse Table

시간 제한30초메모리 제한2048 MB

요약
0에서 n까지의 경로만 있는 방향 그래프에서 a→b와 b→c가 있으면 a→c를 추가하는 연산만으로 모든 v가 뒤쪽 u에 세 간선 이내로 도달하도록 만들어야 한다.
난이도

어려움10점 중 9점

유형
그래프, 분할 정복, 구현, 수학
정답자
아직 제출이 없습니다

문제

This is an interactive problem.

You are given a directed graph GG on vertices numbered 00 to nn. Initially, GG contains exactly nn edges of the form v→v+1v \to v + 1. Your task is to add some edges to this graph in such a way that for every two vertices v,uv, u (v<uv < u) there exists a directed path from vv to uu consisting of at most three edges. There are also two additional requirements you must meet:

  1. You can add an edge a→ca \to c if and only if there exists such bb that edges a→ba \to b and b→cb \to c are already present in GG.
  2. You can add at most 6⋅n6 \cdot n edges in total.

예제1

  1. 예제 1

    입력
    9
    
    
    
    
    
    
    
    3
    1 8
    2 4
    0 5
    
    예상 출력
    7
    1 2 3
    0 1 3
    6 7 8
    6 8 9
    3 4 5
    4 5 6
    3 5 6
    
    1 3 6 8
    2 3 4
    0 1 3 5