Submission #320440

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
320440	2020-11-08 18:56:38	mihai145	Werewolf (IOI18_werewolf)	C++14	100 / 100	3044 ms	314656 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
#include "werewolf.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
const int NMAX = 2e5;
const int LOGMAX = 18;
int _N, M, Q;
std::vector <int> g[NMAX + 2];
int dadSmall[NMAX + 2], dadBig[NMAX + 2];
std::vector <int> dsuSmall[NMAX + 2]; ///in subtree[x] am toate nodurile reach-able <= x
std::vector <int> dsuBig[NMAX + 2]; ///in subree[x] am toate nodurile reach-able >= x
int RootSmall(int x) {
    if(x == dadSmall[x])
        return x;
    return dadSmall[x] = RootSmall(dadSmall[x]);
}
int RootBig(int x) {
    if(x == dadBig[x])
        return x;
    return dadBig[x] = RootBig(dadBig[x]);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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