Submission #83512

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
83512	2018-11-08 14:52:28	radoslav11	Werewolf (IOI18_werewolf)	C++14	100 / 100	1203 ms	157044 KiB

werewolf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
    We build a prefix and suffix tree with dsu, by incrementing them by 1 vertex at each step. Now queries become:
    Do two subtrees have a common vertex (the first subtree is from the prefix tree and the second subtree is from the suffix tree).
    This can be done with DFS order + dsu on tree by keeping a set for each vertex. The complexity will be O(N log^2 N + Q log N).
*/
#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
using namespace std;
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 18);
int tp[MAXN], sz[MAXN], par[MAXN];
void init(int n)
{
    for(int i = 0; i <= n; i++)
        par[i] = i, sz[i] = 1, tp[i] = i;
}
int root(int x) { return x == par[x] ? x : (par[x] = root(par[x])); }
bool connected(int u, int v)
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51