Submission #806589

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
806589	2023-08-04 08:10:44	Trisanu_Das	Werewolf (IOI18_werewolf)	C++17	100 / 100	629 ms	158876 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>
#include "werewolf.h"
using namespace std; 
 
#define vi vector<int>
 
const int mx = 6e5 + 5;
 
int par[mx], tin[mx], tout[mx], ti, id; vector<int> dsuAdj[mx]; set<int> nodes[mx];
 
int get(int i){ 
    return i == par[i] ? i : par[i] = get(par[i]); 
}
void merge(int a, int b, bool build){
    a = get(a); b = get(b); if (a == b) return;
    if (build){
        dsuAdj[id].push_back(a); dsuAdj[id].push_back(b);
        par[a] = par[b] = id++;
    }
    else{
        if (nodes[a].size() > nodes[b].size()) swap(a, b); 
        par[a] = b;
        nodes[b].insert(nodes[a].begin(), nodes[a].end());
    }
}
void dfs(int i){
    tin[i] = ti++;
    for (int x : dsuAdj[i]) dfs(x);
    tout[i] = ti - 1;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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