Gotham PD

All submissions for this problem are available.
Read problems statements in russian and vietnamese as well.
Chef has teamed up with Batman and Jim Gordon to save Gotham from Joker's plan.
There are initially N police stations each having a unique id and an encryption key. All stations are connected, using telephone lines, directly or indirectly, to Gordon's police station (the one with id R). In order to provide better protection for all people in Gotham, Batman and Chef have paid for some new police stations and come up a smart algorithm to test the security of a particular police station.
There are Q queries that the two of them perform on Gotham's infrastructure each being either an addition of a new police station or a security test, on a particular station, using a key generated by Chef.
Your task is to help our three heroes to perform all the queries succesfully and defeat Joker.
Input
There is only one test case in each test file.
The first line contains two numbers, N and Q, denoting the number of police stations and the number of queries respectively.
The second line contains two numbers, R and key, denoting the main station's id and its encryption key.
Each of the next N1 lines contains three numbers: u, v, k which represent that there is a telephone line from v to u and that u's encryption key is k.
Each of the next Q lines contains a query of form:
 0 v u k: A new station with id u and encryption key k is added and connected by a telephone line to v
 1 v k: The security test needs two encryption keys a and b such that a minimizes the value of a xor k and b that maximizes the value of b xor k. a and b are encryption keys that correspond to some nodes that lie on the path, formed by telephone lines, from police station v to Gordon's police station, R.
The problem requires an online solution. Each query will be encoded using the xor between its real values and the value of the last answer. Please see the note section at the end of the statement to see a piece of code that shows how the input should be read.
Output
For each operation of type 1, output a single line containing the two requested values (minvalue and maxvalue) separated by a single space.
Constraints
 1 ≤ N ≤ 100,000
 1 ≤ Q ≤ 200,000
 1 ≤ R, u_{i}, v_{i}, key, k_{i} ≤ 2^{31}− 1
 All ids are unique (there aren't at any time two police stations with the same id).
 Whenever you have to connect a node u to another one v, it is guaranteed that v is already connected, directly of indirectly, to R.
Subtasks
Subtask #1 (30 points):
 1 ≤ N ≤ 5000
 1 ≤ Q ≤ 5000
Subtask #2 (70 points):
 Original constraints
Example
Input: 6 4 1 2 5 1 3 2 1 4 3 2 5 4 2 1 6 3 3 1 4 2 6 0 12 0 7 12 7 4 0 7 Output: 0 6 2 7 0 1
Explanation
Initially, there are 6 police stations in Gotham and our heroes have 4 operations to perform Gordon's station is the one that has id 1 and key 2.
First query: The values on the path from 4 to 1 are 1 xor 2 = 3, 4 xor 2 = 6 and 2 xor 2 = 0. The answer is 0 6.
Second query: The values on the path from 10 to 1 are 6 xor 1 = 7, 3 xor 1 = 2, 5 xor 1 = 4, 4 xor 1 = 5 and 2 xor 1 = 3. The answer is 2 7.
Third query: The values on the path from 5 to 1 are 3 xor 2 = 1 and 2 xor 2 = 0. The answer is 0 1.
The decoded version of all operations is:
1 4 2 (t v k) 0 6 10 6 (t v u k) 1 10 1 (t v k) 1 5 2 (t v k)
Note
cin >> N >> Q;
cin >> R >> key;
for (i = 0; i < N  1; i++)
{
cin >> u >> v >> k;
}
int last_answer = 0;
for (i = 0; i < Q; i++)
{
cin >> t;
// find real value of t
t ^= last_answer;
if (t == 0)
{
cin >> v >> u >> k;
// find real values for u, v, and k
u ^= last_answer;
v ^= last_answer;
k ^= last_answer;
}
else
{
cin >> v >> k;
// find real values for v, and k
v ^= last_answer;
k ^= last_answer;
// compute the requested values
int min_answer = ...
int max_answer = ...
// update last_answer
last_answer = min_answer ^ max_answer;
}
}
Author:  alexvaleanu 
Tags  alexvaleanu 
Date Added:  4052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions