Hula's Cardgame

시간 제한2초메모리 제한512 MB

요약
각 목표 테이블 E마다, 상대가 매 턴 카드 한 장을 제거하는 상황에서 첫 번째 플레이어가 1번 테이블에서 E로 강제로 이동할 수 있는지 판정한다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 동적 계획법, 게임 이론
정답자
아직 제출이 없습니다

문제

근수와 승형이는 K512에서 Hula's Cardgame을 즐기려고 한다. K512에는 NN개의 테이블이 있고 각 테이블은 11부터 NN까지의 번호가 차례대로 부여되어 있다. 각 테이블 위에는 33장의 카드가 있고 ii번 테이블 위 33장의 카드에는 각각 ii 이상 NN 이하인 정수가 적혀 있다.

현재 근수와 승형이는 11번 테이블에 있다. EE번 테이블에는 근수가 좋아하는 도마 우마루 인형이 있어서 근수는 EE번 테이블로 이동하고 싶어 한다. 승형이는 이러한 근수가 못마땅한지 EE번 테이블로 이동하고 싶어 하지 않는다. 근수와 승형이는 다음과 같은 행동을 게임이 끝나기 전까지 반복한다.

  1. 현재 있는 테이블이 EE번 테이블이라면 근수가 게임에서 승리한다.
  2. 현재 있는 테이블이 EE번 테이블이 아니라면, 승형이가 현재 있는 테이블 위 33장의 카드 중 하나를 제거한다.
  3. 근수가 현재 있는 테이블 위에 남아있는 22장의 카드 중 하나를 고른다. 근수와 승형이는 그 카드에 적혀있는 수에 해당되는 번호의 테이블로 이동한다. 만약 근수가 고른 카드에 적힌 수가 현재 있는 테이블의 번호라면 (즉 방문했던 테이블을 재방문하게 되면) 승형이가 게임에서 승리한다.

근수와 승형이가 항상 최선의 전략으로 게임을 한다고 가정할 때 근수는 자신이 게임에서 이길 수 있는지 궁금해한다. 이러한 문제 하나를 풀어내는 것은 여기까지 문제를 풀어온 당신한테는 너무 쉬운 문제일 것이다. 모든 EE (1≤E≤N)(1 \le E \le N)에 대해서 문제를 풀어내 보자!

입력

첫 번째 줄에 테이블의 개수 NN이 주어진다. (1≤N≤2×1051 \le N \le 2\times10^5)

두 번째 줄부터 N+1N+1 번째 줄까지 테이블 위 33장의 카드에 적혀있는 정수 a_i,b_i,c_ia\_i, b\_i, c\_i가 공백으로 구분되어 주어진다. jj 번째 줄에는 j−1j-1번 테이블 위에 있는 카드 3장에 각각 적힌 정수 3개가 주어진다. (i≤a_i,b_i,c_i≤Ni \le a\_i, b\_i, c\_i \le N)

출력

ii 번째 줄에 E=iE = i일 때 근수가 이길 수 있다면 "Yes"를, 진다면 "No"를 출력한다.

예제2

  1. 예제 1

    입력
    6
    2 3 4
    2 2 3
    4 5 6
    4 5 6
    5 6 6
    6 6 6
    
    예상 출력
    Yes
    No
    No
    No
    No
    Yes
    
  2. 예제 2

    입력
    6
    2 3 4
    2 3 3
    4 5 6
    5 5 5
    6 6 6
    6 6 6
    
    예상 출력
    Yes
    No
    Yes
    No
    Yes
    Yes