Informatica Online Judge

  남남섬 [2112 / 0840]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 11   Total Tried : 12


The Champion of this Problem (C++) : gs16106 - 63ms / 2945byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 신승원)]

Background

한 노인이 다음과 같이 말했다.



자네는 남남섬을 아는가? 맑고 잔잔한 바다로 둘러싸인 참으로 아름다운 섬이라네. 내 거기서 왔지.
하지만 남남섬도 늘 지금 같지는 않았다네. 처음엔 그저 봉우리 몇 개일 뿐이었다네.
그러던 것이, 땅이 솟았는지 바다가 꺼졌는지, 봉우리 사이에 점점 길이 나기 시작한 걸세.
꼭 일 년에 한 쌍씩, 이전까지 이어지지 않았던 봉우리들끼리 이어졌다네.
갈 수 없던 봉우리들끼리 오갈 수 있게 되면서 하나의 마을처럼 뭉치게 되었단 말이야.
상상이 가오? 조그마한 섬의 모습이 드러나기 시작했단 말이지!
그렇게 세월아 네월아 하다보니 지금마냥 하나의 섬이 되었소.
내 그 온 과정을 똑똑히 지켜봤지!

그러고 보니, 궁금한 게 몇 가지 있소.
언제 이어졌는지 궁금한 섬 쌍들이 몇 개 있소만...



그의 말을 가만히 듣다가 정신을 차리고 보니, 나는 어느새 깜빡 잠들어 있었다.
잠에서 깨어 보니 노인은 온데간데없이 홀연히 사라져 있었다.

처음에 N개의 봉우리가 있었고, i번째 해에 봉우리 A_i와 B_i가 이어졌을 때, 두 섬사이의 왕래가 언제 가능해졌는지에 대한 질문 Q개를 답해보자.



이 문제에서는 각각의 질문이 입력으로 주어지는 대신, pseudo-random number generator(PRNG)를 통해 주어진다.
입력 데이터에는 seed가 주어질 것이다.
C++을 사용하는 경우, 여러분의 소스는 다음과 같이 답을 처리하면 된다.

unsigned long long __seed;
void set_seed(int seed){ __seed = seed; }
int poll_next(){
__seed = (__seed * 0x8088405 + 1) % (1ull<<32);
return __seed % N + 1;
}
int main()
{
// ...
// do other things
// ...

int Q, seed;
scanf("%d%d", &Q, &seed);
set_seed(seed);
for(int q = 1; q <= Q; ++q){
int A = poll_next();
int B = poll_next();
// ...
// calculate answer here and save it to "ans"
// ...

printf("%d\n", ans);
__seed += ans;
}
return 0;
}


이 소스에서 A와 B에 담기는 것이 현재 질문에서 알고자 하는 두 봉우리의 번호이다.

참고로, 주어진 PRNG의 작동 구조는 문제를 해결하는 데에 중요하지 않으며, 임의의 입력이 주어져도 해결할 수 있는 알고리즘이 존재한다.
주어진 구조는 각각의 질문과 답이 인과관계를 가지도록 하여, 여러분이 각각의 질문을 순차적으로 대답하도록 강제하기 위함일 뿐임을 참고하라.

Input

첫째 줄에는 봉우리의 수 N이 주어진다. (1 ≤ N ≤ 300,000)
둘째 줄부터 N번째 줄까지는 새롭게 이어진 두 봉우리의 번호 A_i 및 B_i가 주어진다.
(각각의 입력 직전까지는, 그 두 봉우리가 이어지지 않은 상태였음이 보장된다.)
그 뒤에는 질문의 수 Q와 입력을 나타내는 seed 값이 주어진다. (1 ≤ Q ≤ 100,000; 0 ≤ seed ≤ 1,000,000,000)

Output

Q개의 줄에 각각의 질문으로 주어진 두 봉우리 사이를 왕복할 수 있게 된 것이 몇 번째 해인지를 나타내는, 1 이상 N 미만의 정수 하나를 출력하라.
만약 두 봉우리가 같다면 0을 출력한다.

IO Example

입력
4
2 4
4 1
2 3
2
741088667

출력
2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]