# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1220580 | LeonidCuk | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct krt
{
vector<vector<int>>g,lca;
vector<int>dsu,el,er;
int timer=0;
int vfind(int a)
{
if(a==dsu[a])return a;
return dsu[a]=vfind(dsu[a]);
}
void kmerge(int a,int b,bool k)
{
int a1=vfind(a),b1=vfind(b);
if(a1!=b1)
{
if(a1>b1&&k)swap(a1,b1);
else if(k==0&&a1<b1)swap(a1,b1);
dsu[a1]=b1;
g[b1].push_back(a1);
}
}
void dfs(int a,int b)
{
el[a]=timer;timer++;
lca[a][0]=b;
for(int i=1;i<20;i++)
{
lca[a][i]=lca[lca[a][i-1]][i-1];
}
for(auto i:g[a])
{
dfs(i,a);
}
er[a]=timer-1;
}
krt(int n)
{
dsu.resize(n);
g.resize(n);
lca.resize(n,vector<int>(20));
el.resize(n);
er.resize(n);
for(int i=0;i<n;i++)dsu[i]=i;
}
};