Submission #1204185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204185		Abito	Werewolf (IOI18_werewolf)	C++17	In queue	0 ms	0 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
using namespace std;
const int NN=2e6;
int par[22][NN],parr[NN],parrr[NN],n,m,q,t,b[NN],a[NN],sz[NN];
set<int> comp[NN];
vector<int> adj[NN],queries[NN];
bool cmp(pair<int,int> x,pair<int,int> y){
	return min(x.F,x.S)>min(y.F,y.S);
}
int getpar(int x){
	if (x==parr[x]) return x;
	return parr[x]=getpar(parr[x]);
}
void link(int x,int y,int nw){
	x=getpar(x);y=getpar(y);
	a[nw]=min(a[x],a[y]);
	if (x==y){
		adj[nw].pb(x);
		parr[x]=nw;
		return;
	}
	adj[nw].pb(x);adj[nw].pb(y);
	parr[x]=parr[y]=nw;
	return;
}
void dfs(int x){
	b[x]=t++;
	sz[x]=1;
	for (auto u:adj[x]){
		par[0][u]=x;
		dfs(u);
		sz[x]+=sz[u];
	}return;
}
bool cmpp(pair<int,int> x,pair<int,int> y){
	return max(x.F,x.S)>max(y.F,y.S);
}
bool cmppp(vector<int> x,vector<int> y){
	return x[3]<y[3];
}
void build(){
	for (int i=0;i<22;i++) par[i][n+m]=n+m;
	for (int i=1;i<22;i++){
		for (int j=0;j<n+m-1;j++){
			par[i][j]=par[i-1][par[i-1][j]];
		}
	}return;
}
int getparr(int x){
	if (x==parrr[x]) return x;
	return parrr[x]=getparr(parrr[x]);
}
void linkk(int x,int y){
	x=getparr(x);y=getparr(y);
	if (x==y) return;
	if (comp[x].size()>comp[y].size()) swap(x,y);
	for (auto u:comp[x]) comp[y].ep(u);
	parrr[x]=y;
	return;
}
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();q=L.size();
	for (int i=0;i<n+m;i++) parr[i]=i;
	for (int i=0;i<n;i++) a[i]=i;
	vector<pair<int,int>> edges;
	for (int i=0;i<m;i++) edges.pb({X[i],Y[i]});
	sort(edges.begin(),edges.end(),cmp);
	for (int i=0;i<m;i++) link(edges[i].F,edges[i].S,i+n);
	par[0][n+m-1]=n+m;
	dfs(n+m-1);
	/*for (int i=0;i<n+m;i++){
		cout<<i<<":   ";
		for (auto u:adj[i]) cout<<u<<' ';cout<<endl;
	}
	for (int i=0;i<n;i++) cout<<b[i]<<' ';cout<<endl;*/
	vector<int> ans(q);
	sort(edges.begin(),edges.end(),cmpp);
	for (int i=0;i<q;i++) queries[i]={S[i],E[i],L[i],R[i],i};
	sort(queries,queries+q,cmppp);
	/*for (int i=0;i<q;i++){
		for (auto u:queries[i]) cout<<u<<' ';
		cout<<endl;
	}
	for (auto u:edges) cout<<u.F<<' '<<u.S<<endl;*/
	build();
	for (int i=0;i<n;i++) parrr[i]=i,comp[i].ep(b[i]);
	for (int i=0;i<q;i++){
		//cout<<"query "<<i<<endl;
		while (!edges.empty() && max(edges.back().F,edges.back().S)<=queries[i][3]){
			linkk(edges.back().F,edges.back().S);
			//cout<<edges.back().F<<' '<<edges.back().S<<endl;
			edges.ppb();
		}
		int x=queries[i][0];
		for (int j=21;j>=0;j--){
			if (par[j][x]==n+m) continue;
			if (a[par[j][x]]<queries[i][2]) continue;
			x=par[j][x];
		}
		int y=getparr(queries[i][1]);
		//for (auto u:comp[y]) cout<<u<<' ';cout<<endl;
		//cout<<x<<' '<<b[x]<<' '<<b[x]+sz[x]<<endl;
		auto it=comp[y].lower_bound(b[x]);
		if (it==comp[y].end()) continue;
		if (*it<b[x]+sz[x]) ans[queries[i][4]]=1;
	}
	return ans;
}