Codeforces Round 835 (Div. 4)

Dashboard - Codeforces Round 835 (Div. 4) - Codeforces

 

D

함수값이 일정한 부분은 valley 판정에 중요한 부분이 아니다. 중요한 건 양 끝 점이 다음 조건을 만족하는지 여부이다.

따라서 배열 a를 입력받을 때 함수값의 변화가 있는 부분만 받아서 문제를 해결하면 편하다.

 

E

경우의 수를 다루는 문제는 답이 (중간 과정이 모두 int라도) long long일 수 있다.

 

G

a에서 출발하여 인접한 노드로 움직일 때 각 노드에서의 x의 값은 유일하게 결정된다(∵ xor의 항등원이 0). 따라서 각 노드에서의 x 값은 a와 그 노드의 단순 경로의 weight 들로 계산할 수 있다.

먼저 a에서 b로 teleport를 사용하지 않고 이동하는 경우를 살펴보자.
a에서 b의 단순경로의 weight들을 모두 xor한 결과가 0이면 가능하다.

한편, teleport를 사용하여 이동하는 경우를 살펴보자. 편의상, a에서 출발했을 때 임의의 노드 u의 x 값을 Ua,  b에서 출발했을 때 임의의 노드 v의 x값을 Vb로 표기하자.
[어떤 두 노드 u(!= b), v 에 대하여 a->u, v->b, Ua = Vb]라고 하자. 그러면 a에서 u로 이동 후 v로 teleport 하고 b로 이동할 수 있다.
역도 성립하므로 위 성질을 만족하는 두 노드 u, v가 존재하는지 확인하면 된다.