Submission #678353

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
678353	2023-01-05 14:13:21	1bin	Werewolf (IOI18_werewolf)	C++14	100 / 100	846 ms	116992 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 <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1 << 18;
ll n, m, q, par[B], a, b, d[B][2], u[B][2], t;
vector<int> adj[B], seg[B * 2];
vector<int> g[B], vl[B], vr[B];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}
void dfs(int x, int f){
    !f ? d[x][0] = t++ : u[x][0] = t++;
    for(int& nx : g[x]) dfs(nx, f);
    !f ? d[x][1] = t - 1 : u[x][1] = t - 1;
    return;
}
int qry(int l, int r, int k){
    l += B; r += B;
    int ret = n;
    while(l <= r){
        if(l & 1){
            auto it = lower_bound(all(seg[l]), k);
            if(it != seg[l].end()) ret = min(ret, *it);
            l++;
        }
        if(!(r & 1)){
            auto it = lower_bound(all(seg[r]), k);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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