Submission #601883

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
601883	2022-07-22 11:44:09	idiot123	Werewolf (IOI18_werewolf)	C++14	100 / 100	963 ms	134512 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<bits/stdc++.h>
using namespace std;
int find(int a, vector<int>& rep){
  if(rep[a] != a)rep[a] = find(rep[a], rep);
  return rep[a];
}
void uni(int a, int b, vector<int>& rep, vector<set<int>>& pos){
  a = find(a, rep); b = find(b, rep);
  if(a != b){
    if(pos[a].size() < pos[b].size())swap(a, b);
    rep[b] = a;
    pos[a].insert(pos[b].begin(), pos[b].end());
    pos[b].clear();
  }
}
void computeRange(int v, vector<pair<int, int>>& children, vector<pair<int, int>>& range, int& cnt){
  if(children[v] == make_pair(-1, -1)){
    range[v] = {cnt, cnt}; cnt++;
  }else{
    computeRange(children[v].first, children, range, cnt);
    computeRange(children[v].second, children, range, cnt);
    range[v] = {range[children[v].first].first, range[children[v].second].second};
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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