Submission #299601

#	Time	Username	Problem	Language	Result	Execution time	Memory
299601		kshitij_sodani	Werewolf (IOI18_werewolf)	C++14	0 / 100	1102 ms	75944 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> 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++){
		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[stt[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;
		}

	}

	return ans;

}

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