| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1234166 | PlayVoltz | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int counter=-1;
vector<int> in, out, dsu, ans, ooga;
vector<vector<int> > graph, query;
vector<set<int> > s;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
bool merge(int a, int b){
a=fp(a), b=fp(b);
if (a==b)return 0;
dsu[a]=b;
return 1;
}
void dfs(int node){
in[node]=++counter;
for (auto num:graph[node])dfs(num);
out[node]=counter;
}
void dfs2(int node){
s[node].insert(in[node]);
for (auto num:graph[node]){
dfs(num);
if (s[node].size()<s[num].size())swap(s[node], s[num]);
for (auto a:s[num])s[node].insert(a);
}
for (auto c:query[node]){
auto it=s[node].lower_bound(in[ooga[c]]);
if (it!=s[node].end()&&*it<=out[ooga[c]])ans[c]=1;
}
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
counter=-1;
in.clear();
out.clear();
graph.clear();
dsu.clear();
ans.clear();
s.clear();
ooga.clear();
query.clear();
query.resize(n);
in.resize(n);
out.resize(n);
graph.resize(n);
dsu.resize(n, -1);
ans.resize(l.size(), 0);
s.resize(n);
ooga.resize(l.size());
vector<vector<int> > adj(n), got(n);
for (int i=0; i<x.size(); ++i)adj[x[i]].pb(y[i]), adj[y[i]].pb(x[i]);
for (int i=0; i<l.size(); ++i)got[l[i]].pb(i);
for (int i=0; i<n; ++i){
for (auto num:adj[i])if (num<i&&merge(i, num))graph[num].pb(i);
for (auto num:got[i])ooga[num]=fp(s[num]);
}
return 0;
dfs(0);
graph.clear();
graph.resize(n);
dsu.clear();
dsu.resize(n, -1);
got.clear();
got.resize(n);
for (int i=0; i<l.size(); ++i)got[r[i]].pb(i);
for (int i=n-1; i>=0; --i){
for (auto num:adj[i])if (num>i&&merge(i, num))graph[num].pb(i);
for (auto num:got[i])query[fp(s[num])].pb(num);
}
dfs2(n-1);
return ans;
}