| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1280208 | MMihalev | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
#include<iostream>
#include<vector>
#include<tuple>
#include<cmath>
#include<bitset>
#include<algorithm>
//#include "werewolf.h"
using namespace std;
const int MAX_N=2e5+5;
const int MAX_M=4e5+5;
const int NLOG=3600000;
const int BLOCK_SIZE=5000;
int n,m,q;
vector<int>g[MAX_N];
int l[MAX_N];
int r[MAX_N];
int s[MAX_N];
int e[MAX_N];
vector<int>forleft[MAX_N],forright[MAX_N];
vector<pair<int,int>>queries;
int pare[MAX_N];
///init
vector<pair<int,int>>updates1[MAX_N],updates2[MAX_N];
int upd2id[MAX_N];
int prevblockcnt[MAX_N];
bitset<MAX_N>blockqueries[NLOG/BLOCK_SIZE];
///blocks
int parent[MAX_N],sz[MAX_N];
int curtime;
int Find(int u)
{
if(parent[u]==u)return u;
return parent[u]=Find(parent[u]);
}
void Merge(int u,int v,bool f)
{
int urt=Find(u),vrt=Find(v);
if(urt==vrt)return;
if(sz[urt]>sz[vrt])swap(urt,vrt);
parent[urt]=vrt;
sz[vrt]+=sz[urt];
if(f)
{
for(auto [node,useless]:updates[urt])
{
updates1[vrt].push_back({node,curtime});
}
}
else
{
for(auto [node,useless]:updates[urt])
{
updates2[node].push_back({vrt,curtime});
}
}
}
///dsu
void Update(int query)
{
int node=pare[query];
int posr,br;
int ll=0,rr=updates1[node].size()-1;
while(ll<=rr)
{
int mid=(ll+rr)/2;
if(updates1[node][mid].second<=r[query])
{
posr=mid;
ll=mid+1;
}
else rr=mid-1;
}
br=posr/BLOCK_SIZE;
for(int b=0;b<br;b++)
{
blockqueries[prevblockcnt[node]+b+1][query]=1;
}
int u,v;
for(int i=br*BLOCK_SIZE;i<=posr;i++)
{
u=updates1[node][i].first;
while(upd2id[u]+1<updates2[u].size() && updates2[u][upd2id[u]+1].second>=l[query])
{
upd2id[u]++;
}
v=s[query];
while(upd2id[v]+1<updates2[v].size() && updates2[v][upd2id[v]+1].second>=l[query])
{
upd2id[v]++;
}
if(updates2[u][upd2id[u]].second>=l[query] && updates2[v][upd2id[v]].second>=l[query] &&
updates2[u][upd2id[u]].first==updates2[v][upd2id[v]].first)ans[query]=1;
}
}
vector<int>nodes;
vector<int>ans;
bool active[MAX_N];
bool used[MAX_N];
void dfs(int u)
{
used[u]=1;
for(int v:g[u])
{
if(v>=curtime && !used[v])dfs(v);
}
}
void bfs(int block)
{
int idxqueries=0;
for(int i=0;i<n;i++)used[i]=0;
for(int i=n-1;i>=0;i--)
{
if(active[i])used[i]=1;
for(int v:g[i])
{
if(v>i)
{
if(used[v]==used[i])continue;
curtime=i;
if(used[i])dfs(v);
else dfs(i);
}
}
while(idxqueries<q && i==l[idxqueries])
{
if(blockqueries[block][idxqueries] && used[s[idxqueries]])
{
ans[idxqueries]=1;
}
idxqueries++;
}
}
for(int u:nodes)active[u]=0;
nodes.clear();
}
void solve()
{
for(int i=0;i<n;i++)
{
parent[i]=i;
sz[i]=i;
}
updates1[0].push_back({0,0});
for(int i=1;i<n;i++)
{
curtime=i;
updates1[i].push_back({i,i});
for(int v:g[i])
{
if(v<i)
{
Merge(v,i,1);
}
}
for(int query:forright[i])
{
pare[query]=Find(e[query]);
}
}
//int sum=0;
//for(int i=0;i<n;i++)sum+=updates[i].size();
//BLOCK_SIZE=(int)(sqrt(sum));
int curblockcnt=0;
for(int i=0;i<=n;i++)
{
prevblockcnt[i]=curblockcnt;
curblockcnt+=updates[i].size()/BLOCK_SIZE;
}
for(int i=0;i<n;i++)
{
updates2[i].clear();
parent[i]=i;
sz[i]=i;
}
for(int i=n-1;i>=0;i--)
{
curtime=i;
updates2[i].push_back({i,i});
for(int v:g[i])
{
if(v>i)
{
Merge(v,i,0);
}
}
}
for(int i=q-1;i>=0;i--)
{
Update(i);
}
int block=1;
for(int i=0;i<n;i++)
{
int posl=0,posr=BLOCK_SIZE-1;
while(posr<updates[i].size())
{
if(blockqueries[block].any())
{
for(int j=posl;j<=posr;j++)
{
nodes.push_back(updates[i][j].first);
active[updates[i][j].first]=1;
}
bfs(block);
}
block++;
posl+=BLOCK_SIZE;
posr+=BLOCK_SIZE;
}
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R)
{
n=N;
m=X.size();
for(int i=0;i<m;i++)
{
int u=X[i],v=Y[i];
g[u].push_back(v);
g[v].push_back(u);
}
q=S.size();
ans.resize(q);
for(int i=0;i<q;i++)
{
queries.push_back({L[i],i});
}
sort(queries.rbegin(),queries.rend());
for(int i=0;i<q;i++)
{
int id=queries[i].second;
s[i]=S[id];e[i]=E[id];l[i]=L[id];r[i]=R[id];
forleft[l[i]].push_back(i);
forright[r[i]].push_back(i);
}
solve();
auto ans2=ans;
for(int i=0;i<q;i++)
{
int id=queries[i].second;
ans[id]=ans2[i];
}
return ans;
}