시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.75 초 (추가 시간 없음) | 8 MB (추가 메모리 없음) | 191 | 79 | 73 | 48.993% |
메모리 제한에 주의하세요
엄청나게 머나 먼 미래, 새로운 삶의 터전을 찾아 떠난 인류는 고대에 엄청나게 큰 뱀이 살았다는 빌라봉 행성을 발견한다. 빌라봉 행성은 대부분 바다여서 모든 땅은 섬이었지만, 고도로 발전된 기술 덕분에 인류는 빌라봉 행성에 쉽게 정착할 수 있었다. 하지만 잦은 다툼 때문에 하나로 합치지 못하고 서로 다른 나라를 세워 살게 되었다.
각 나라는 한 개 이상의 섬을 지배하고 있고, 어떤 나라에도 속하지 않은 섬은 없으며, 하나의 섬은 두 개 이상의 나라가 지배할 수 없다.
섬은 여러 개의 도시와 서로 다른 도시를 잇는 도로로 이루어져 있다. 같은 섬에서 임의의 두 도시 사이의 경로는 항상 유일하다.
기술이 고도로 발전했기 때문에 섬 사이를 잇는 도로를 만들어, 서로 떨어져 있던 섬들을 하나로 합칠 수 있다. 빌라봉 행성의 섬나라들은 주변국과 사이가 좋지 않기 때문에, 서로 다른 두 나라의 섬을 잇는 도로는 만들 수 없다. 또한 이미 경로가 존재하는 두 도시를 잇는 도로를 만드는 것은 비효율적이기 때문에, 같은 섬의 두 도시를 잇는 도로는 만들지 않는다.
때때로 빌라봉 행성의 특정 지역에는 빌라봉온난화 현상으로 해수면이 상승해 도로가 파괴될 수 있다. 이 경우 하나의 섬이 여러 개의 섬으로 나뉘고, 나뉜 섬들은 기존 섬을 지배하던 나라가 지배한다.
빌라봉 행성의 저명한 지리학자 기웅이는 특정 시점에 각 나라가 몇 개의 섬을 지배하고 있는지 궁금해졌다. 기웅이에게는 어려운 문제이지만, 똑똑한 여러분은 해낼 수 있을 거라 믿는다!
첫째 줄에 나라의 개수 $N$이 주어진다. 각 나라는 $1$이상 $N$이하의 정수로 나타낸다. ($1 \leq N \leq min(193^ 2, \sum V)$, $\sum V \leq 1\ 000\ 000$)
둘째 줄부터는 $N$개의 나라에 대한 정보가 주어진다. 각 나라에 해당하는 첫째 줄에는 도시의 개수 $V_i$와 초기 도로의 개수 $E_i$가 주어지고, 각 나라의 도시는 $\sum^{i-1} V + 1$부터 $\sum^i V$ 까지 정수로 나타낸다. ($0 \leq E_i < V_i$)
다음 $E_i$개 줄에는 같은 나라의 서로 다른 도시를 잇는 도로의 정보가 주어진다. 같은 섬에서 임의의 두 도시 사이의 경로는 항상 유일하다.
다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \leq Q \leq 100\ 000$)
다음 $Q$개 줄에는 쿼리가 주어진다. 쿼리는 다음 $3$가지 형태 중 하나다.
$1$번 쿼리가 주어질 때마다, $k$번 나라가 지배하는 섬의 수를 출력한다.
2 2 1 1 2 4 2 3 5 3 4 4 2 1 2 3 3 6 1 1 1 2
2 1
4 5 3 1 2 1 3 5 4 3 0 5 4 10 9 10 11 10 12 10 13 6 5 15 16 16 17 17 18 17 19 14 19 13 1 2 2 16 17 2 9 10 1 4 2 10 12 3 9 12 1 3 3 1 5 1 1 3 14 15 2 1 2 1 1 1 4
3 2 2 1 2 1
$193$은 문제 출제 시점, UN에 가입한 정회원국의 수이다.
University > 연세대학교 > 2021 연세대학교 프로그래밍 경진대회 G번
C++17, C11, C99, C++11, C++14, C++20