Submission #694132

#	Time	Username	Problem	Language	Result	Execution time	Memory
694132		amirhoseinfar1385	Werewolf (IOI18_werewolf)	C++17	100 / 100	1143 ms	133012 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn=200000+5;
vector<int>adj[maxn];
struct dsu{
	int par[maxn],sz[maxn],lca[maxn][20],fpar[maxn];
	vector<int>child[maxn];
	pair<int,int>stf[maxn];
	int timea;
	dsu(){
	    for(int i=0;i<maxn;i++){
	        for(int j=0;j<20;j++){
	            lca[i][j]=-1;
	        }
	    }
		timea=0;
		for(int i=0;i<maxn;i++){
			par[i]=i;
			fpar[i]=i;
		}
	}
	int root(int c){
		if(fpar[c]==c){
			return c;
		}
		return fpar[c]=root(fpar[c]);
	}
	void con(int u,int v,int vv){
		int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
		    if(vv==0){
		        if(rootu<rootv){
		            swap(rootu,rootv);
		        }
		    }
		    else{  
		        if(rootu>rootv){
		            swap(rootu,rootv);
		        }
		    }
			par[rootv]=rootu;
			child[rootu].push_back(rootv);
			fpar[rootv]=rootu;
		}
	}
	void dfs(int u){
		timea++;
		stf[u].first=timea;
		for(auto x:child[u]){
		    lca[x][0]=u;
//		    cout<<u<<" "<<x<<" "<<timea<<endl;
			dfs(x);
		}
		stf[u].second=timea;
	}
	void build(){
		int rishe=root(1);
		dfs(rishe);
		for(int i=1;i<20;i++){
		    for(int j=0;j<maxn;j++){
		        if(lca[j][i-1]==-1){
		            continue;
		        }
		        lca[j][i]=lca[lca[j][i-1]][i-1];
		    }
		}
	}
	int ww(int u,int had,int vv){
		for(int i=19;i>=0;i--){
		    if(lca[u][i]!=-1){
//		        cout<<u<<" "<<vv<<" "<<lca[u][i]<<endl;
		        if(vv==0){
		            if(lca[u][i]<=had){
		                u=lca[u][i];
		            }
		        }
		        else{
		            if(lca[u][i]>=had){
		                u=lca[u][i];
		            }
		        }
		    }
		}
		return u;
	}
};
int kaf=(1<<18);
struct segment{
	struct node{
		vector<int>all;
	};
	node seg[(1<<19)];
	vector<int>merge(vector<int>a,vector<int>b){
		vector<int>ret;
		int i=0,j=0;
		while(i<(int)a.size()&&j<(int)b.size()){
			if(a[i]<b[j]){
				ret.push_back(a[i]);
				i++;
			}
			else{
				ret.push_back(b[j]);
				j++;
			}
		}
		while(i<(int)a.size()){
			ret.push_back(a[i]);
			i++;
		}
		while(j<(int)b.size()){
			ret.push_back(b[j]);
			j++;
		}
		return ret;
	}
	void build(int i){
		if((i<<1)>=(1<<19)){
			return ;
		}
		build((i<<1));
		build((i<<1)^1);
		seg[i].all=merge(seg[(i<<1)].all,seg[(i<<1)^1].all);	
	}
	int pors(int i,int l,int r,int tl,int tr,int hl,int hr){
		if(l>tr||r<tl){
			return 0;
		}
		if(l>=tl&&r<=tr){
			int p=lower_bound(seg[i].all.begin(),seg[i].all.end(),hl)-seg[i].all.begin();
	//		cout<<l<<" dsa "<<r<<" "<<tl<<" "<<tr<<" "<<hl<<" "<<hr<<endl;
	//		for(auto x:seg[i].all){
	//		    cout<<x<<" ";
	//		}
	//		cout<<"by"<<endl;
			if(p==(int)seg[i].all.size()){
				return 0;
			}
			if(seg[i].all[p]<=hr){
				return 1;
			}
			return 0;
		}
		int m=(l+r)>>1;
		int d=pors((i<<1),l,m,tl,tr,hl,hr);
		d|=pors((i<<1)^1,m+1,r,tl,tr,hl,hr);
		return d;
	}
};
dsu a,b;
segment seg;

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
	int m=x.size();
	for(int i=0;i<m;i++){
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	for(int i=0;i<=n-1;i++){
		for(auto x:adj[i]){
			if(x<=i){
				a.con(x,i,0);
			}
		}
	}
	for(int i=n-1;i>=0;i--){
		for(auto x:adj[i]){
			if(x>=i){
				b.con(x,i,1);
			}
		}
	}
	a.build();
	b.build();
	for(int i=0;i<n;i++){
		seg.seg[kaf+a.stf[i].first].all.push_back(b.stf[i].first);
	//	cout<<i<<" asd "<<a.stf[i].first<<" "<<b.stf[i].first<<endl;
	}
	seg.build(1);
	int q=s.size();
	vector<int>res(q);
	for(int i=0;i<q;i++){
		int u=s[i],v=e[i],tl=l[i],tr=r[i];
		if(u<tl||v>tr){
			res[i]=0;
			continue;
		}
		int bu=b.ww(u,tl,1),bv=a.ww(v,tr,0);
		int d=seg.pors(1,0,kaf-1,a.stf[bv].first,a.stf[bv].second,b.stf[bu].first,b.stf[bu].second);
		res[i]=d;
//		cout<<bu<<" "<<bv<<" "<<u<<" "<<v<<" "<<tl<<" "<<tr<<endl;
	}
	return res;	
}

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