제출 #299610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299610		kshitij_sodani	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1195 ms	141540 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;


#include "werewolf.h"
vector<pair<int,int>> pre[200001];
vector<pair<int,int>> pre2[200001];
vector<pair<int,int>> pre3[200001];
vector<pair<int,int>> pre4[200001];

int par[200001];
int ss[200001];
vector<int> adj[200001];
vector<int> adj2[200001];

int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int co=-1;
int st[200001];
int stt[200001];
void dfs(int no){
	co++;
	st[no]=co;
	stt[co]=no;
	for(auto j:adj[no]){
		dfs(j);
	}
}
int co2=-1;
int st2[200001];
int stt2[200001];
void dfs2(int no){
	co2++;
	st2[no]=co2;
	stt2[co2]=no;

	for(auto j:adj2[no]){
		dfs2(j);
	}

}

pair<int,int> ran[200001];
pair<int,int> ran2[200001];
int vis[200001];

vector<int> tree[800001];
void add(int no,int l,int r,int aa,int bb,int i){
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		tree[no].pb(i);
	}
	else{
		int mid=(l+r)/2;
		add(no*2+1,l,mid,aa,bb,i);
		add(no*2+2,mid+1,r,aa,bb,i);
	}
}
int ans2[200001];
void update(int no,int l,int r,int i){
	for(auto j:tree[no]){
		if(vis[j]==0){
			ans2[j]=1;
		}
	}
	tree[no].clear();
	if(l<r){
		int mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i);
		}
		else{
			update(no*2+2,mid+1,r,i);
		}
	}
}
//vector<int> pre5[200001];

vector<pair<pair<int,int>,int>> pre5[200001];
vector<int> pre6[200001];
vector<int> check_validity(int n,vector<int> xx,vector<int> yy,
                                vector<int> ss3,vector<int> ee,
                                vector<int> l,vector<int> r) {
	int m=xx.size();
	for(int i=0;i<m;i++){
		pre[min(xx[i],yy[i])].pb({xx[i],yy[i]});
		pre2[max(xx[i],yy[i])].pb({xx[i],yy[i]});
	}
	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=1;
	}
	int q=ss3.size();
	for(int i=0;i<q;i++){
		pre3[l[i]].pb({ss3[i],i});
		pre4[r[i]].pb({ee[i],i});
	}
	vector<pair<pair<int,int>,int>> qq;
	for(int i=n-1;i>=0;i--){
		for(auto j:pre[i]){
			int x=find(j.a);
			int y=find(j.b);
			if(x!=y){
			//	cout<<x<<":"<<y<<endl;
				adj[x].pb(y);
				par[y]=x;
				ss[x]+=ss[y];
			}
		}
		for(auto j:pre3[i]){
			qq.pb({{find(j.a),ss[find(j.a)]},j.b});
		//	cout<<j.a<<"."<<find(j.a)<<"/"<<ss[find(j.a)]<<"/"<<j.b<<endl;
		}
	}
	dfs(find(0));
	for(auto j:qq){
		ran[j.b]={st[j.a.a],st[j.a.a]+j.a.b-1};
	}
	/*for(int i=0;i<q;i++){
		cout<<ran[i].a<<":"<<ran[i].b<<endl;
		for(int j=ran[i].a;j<=ran[i].b;j++){
			cout<<stt[j]<<",";
		}
		cout<<endl;
	}*/
	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=1;
	}
	vector<pair<pair<int,int>,int>> qq2;
	for(int i=0;i<n;i++){
		for(auto j:pre2[i]){
			int x=find(j.a);
			int y=find(j.b);
			if(x!=y){
				adj2[x].pb(y);
				//cout<<x<<":"<<y<<endl;
				par[y]=x;
				ss[x]+=ss[y];
			}
		}
		for(auto j:pre4[i]){
			qq2.pb({{find(j.a),ss[find(j.a)]},j.b});
		}
	}
	dfs2(find(0));
	for(auto j:qq2){
		ran2[j.b]={st2[j.a.a],st2[j.a.a]+j.a.b-1};
	}




	vector<int> ans;
	for(int i=0;i<q;i++){
		pre5[ran[i].a].pb({ran2[i],i});
		pre6[ran[i].b].pb(i);
		/*for(int j=ran[i].a;j<=ran[i].b;j++){
			vis[stt[j]]+=1;
		}
		int kk=0;
		for(int j=ran2[i].a;j<=ran2[i].b;j++){
			vis[stt2[j]]+=1;
			if(vis[stt2[j]]==2){
				kk=-1;
			}
		}
		ans.pb(kk);
		for(int j=ran[i].a;j<=ran[i].b;j++){
			vis[stt[j]]-=1;
		}
		for(int j=ran2[i].a;j<=ran2[i].b;j++){
			vis[stt2[j]]-=1;
		}*/

	}
	for(int i=0;i<n;i++){
		for(auto j:pre5[i]){
			add(0,0,n-1,j.a.a,j.a.b,j.b);
		}
		update(0,0,n-1,st2[stt[i]]);



		for(auto j:pre6[i]){
			vis[j]=1;
		}
	}
	for(int i=0;i<q;i++){
		ans.pb(ans2[i]);
	}

	return ans;

}

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