| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 125 | 46 | 43 | 35.537% |
정점 $N$개와 단방향 간선 $M$개로 이루어져 있는 유향 그래프가 있다. 같은 출발점과 도착점 사이에 여러 개의 간선이 있을 수 있고, 간선의 출발점과 도착점이 같을 수 있다.
각 간선에는 $x, y, z$ 중 하나의 문자가 쓰여 있다. 이때, 한 정점에서 뻗어나오는 간선의 문자는 서로 겹치지 않는다.
이후 다음과 같은 쿼리가 주어진다.
그래프에서 이동할 때는 특별한 규칙을 따른다. 구체적으로, $x$ 간선 이후에는 $y$ 간선, $y$ 간선 이후에는 $z$ 간선, $z$ 간선 이후에는 $x$ 간선을 타고 이동해야 한다. 즉, $xyzxyzxyz\cdots,ドル$ yzxyzxyzx\cdots,ドル $zxyzxyzxy\cdots$의 방식으로만 이동할 수 있다.
쿼리 $Q$개가 주어질 때, 이를 해결하는 프로그램을 작성해보자. 단, 각 쿼리는 독립적이며, 이전 쿼리에서 추가된 간선이 다음 쿼리에 적용되지 않는다.
첫 번째 줄에 $N, M, Q$가 주어진다.(1ドル \leq N \leq 100000,ドル 1ドル \leq M \leq 3 \times N,ドル 1ドル \leq Q \leq 100000$)
이후 두 번째 줄부터 $M + 1$번째 줄까지 그래프의 간선의 정보 $S_i, E_i, C_i$가 주어진다. 이는 $S_i$에서 $E_i$로 가는 $C_i$가 쓰여진 간선을 의미한다.(1ドル \le S_i, E_i \le N,ドル $C_i \in \{x,y,z\}$)
이후 $M + 2$번째 줄부터 $M + Q + 1$번째 줄까지 쿼리의 정보 $s, e, c$가 주어진다.(1ドル \le s, e \le N,ドル $c \in \{x,y,z\}$)
$Q$줄에 걸쳐 $i$번째 줄에 $i$번째 쿼리에 대해 각각 무한히 이동 가능하다면 1ドル,ドル 그렇지 않으면 0ドル$을 출력한다.
2 1 1 1 2 x 1 2 x
0
1ドル$번 예제에서는 어떤 쿼리에서도 1ドル(x) \rightarrow 2(y)$까지만 이동할 수 있다.
3 3 3 1 2 x 2 3 y 3 1 z 1 2 x 2 3 x 3 1 x
1 1 1
2ドル$번 예제에서는 원래부터 1ドル(x) \rightarrow 2(y) \rightarrow 3(z) \rightarrow 1(x) \rightarrow 2(y) \rightarrow 3(z) \rightarrow \cdots $ 의 이동이 가능하므로, 어떤 쿼리에서도 무한히 이동 가능하다.
5 2 3 1 2 x 2 3 y 1 2 x 3 1 z 3 2 y
0 1 0
3ドル$번 예제에서는 2번째 쿼리에서만 1ドル(x) \rightarrow 2(y) \rightarrow 3(z) \rightarrow 1(x) \rightarrow 2(y) \rightarrow 3(z) \rightarrow \cdots $ 의 이동이 가능하다. 나머지 간선에서는 무한히 이동할 수 없다.
School > 경기과학고등학교 > 나는코더다 2022 송년대회 F번