Submission #88843

#	Time	Username	Problem	Language	Result	Execution time	Memory
88843		dsjong	Werewolf (IOI18_werewolf)	C++14	15 / 100	2462 ms	41900 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj1[3005];
vector<int>adj2[3005];
vector<int>adj3[200001];
bool b=false;
bool vis1[3005];
bool vis2[3005];
bool vis3[200001];
int cnt[200001];
vector<int>v;
int rv[200001];
int seg1[600000];
int seg2[600000];
void dfs1(int cur,int par){
	vis1[cur]=1;
	for(int i:adj1[cur]){
		if(i!=par&&!vis1[i]){
			dfs1(i,cur);
		}
	}
}
void dfs2(int cur,int par){
	vis2[cur]=1;
	if(vis1[cur]){
		b=true;
		return;
	}
	for(int i:adj2[cur]){
		if(i!=par&&!vis2[i]){
			dfs2(i,cur);
		}
	}
}
void dfs3(int cur,int par){
	vis3[cur]=1;
	for(int i:adj3[cur]){
		if(i!=par&&!vis3[i]){
			v.push_back(i);
			rv[i]=v.size()-1;
			dfs3(i,cur);
		}
	}
}
void build1(int L,int R,int node){
	if(L==R){
		seg1[node]=v[L];
		return;
	}
	build1(L,(L+R)/2,2*node);
	build1((L+R)/2+1,R,2*node+1);
	seg1[node]=min(seg1[2*node],seg1[2*node+1]);
}
void build2(int L,int R,int node){
	if(L==R){
		seg2[node]=v[L];
		return;
	}
	build2(L,(L+R)/2,2*node);
	build2((L+R)/2+1,R,2*node+1);
	seg2[node]=max(seg2[2*node],seg2[2*node+1]);
}
int query1(int A,int B,int L,int R,int node){
	if(R<A||B<L){
		return 1e9;
	}
	else if(A<=L&&B>=R){
		return seg1[node];
	}
	else{
		return min(query1(A,B,L,(L+R)/2,2*node),query1(A,B,(L+R)/2+1,R,2*node+1));
	}
}
int query2(int A,int B,int L,int R,int node){
	if(R<A||B<L){
		return -1e9;
	}
	else if(A<=L&&B>=R){
		return seg2[node];
	}
	else{
		return max(query2(A,B,L,(L+R)/2,2*node),query2(A,B,(L+R)/2+1,R,2*node+1));
	}
}
int bsearch1(int s,int e,int l,bool b){
	if(query1(s,e,0,v.size()-1,1)>=l){
		if(b) return e+1;
		return e-1;
	}
	if(b){
		int m=(s+e)/2;
		if(e-s<=1){
			if(v[s]<l){
				return s;
			}
			return e;
		}
		if(query1(s,m,0,v.size()-1,1)<l){
			return bsearch1(s,m,l,b);
		}
		return bsearch1(m,e,l,b);
	}
	else{
		int m=(s+e)/2;
		if(s-e<=1){
			if(v[s]<l){
				return s;
			}
			return e;
		}
		if(query1(m,s,0,v.size()-1,1)<l){
			return bsearch1(m,s,l,b);
		}
		return bsearch1(e,m,l,b);
	}
}
int bsearch2(int s,int e,int r,bool b){
	if(query2(s,e,0,v.size()-1,1)<=r){
		if(b) return s-1;
		return s+1;
	}
	if(b){
		//search from right
		int m=(s+e)/2;
		if(e-s<=1){
			if(v[e]>r){
				return e;
			}
			return s;
		}
		if(query2(m,e,0,v.size()-1,1)>r){
			return bsearch2(m,e,r,b);
		}
		return bsearch2(s,m,r,b);
	}
	else{
		int m=(s+e)/2;
		if(s-e<=1){
			if(v[e]>r){
				return e;
			}
			return s;
		}
		if(query2(e,m,0,v.size()-1,1)>r){
			return bsearch2(e,m,r,b);
		}
		return bsearch2(m,s,r,b);
	}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	vector<int>ans;
	if(N<=3000){
		for(int i=0;i<L.size();i++){
			memset(vis1,0,sizeof vis1);
			memset(vis2,0,sizeof vis2);
			int l=L[i],r=R[i],s=S[i],e=E[i];
			for(int j=0;j<=3000;j++){
				adj1[j].clear();
				adj2[j].clear();
			}
			for(int j=0;j<X.size();j++){
				if(X[j]>=l&&Y[j]>=l){
					adj1[X[j]].push_back(Y[j]);
					adj1[Y[j]].push_back(X[j]);
				}
				if(X[j]<=r&&Y[j]<=r){
					adj2[X[j]].push_back(Y[j]);
					adj2[Y[j]].push_back(X[j]);
				}
			}
			b=false;
			dfs1(s,3003);
			dfs2(e,3003);
			if(b){
				ans.push_back(1);
			}
			else{
				ans.push_back(0);
			}
		}
	}
	else{
		for(int i=0;i<X.size();i++){
			cnt[X[i]]++;
			cnt[Y[i]]++;
			adj3[X[i]].push_back(Y[i]);
			adj3[Y[i]].push_back(X[i]);
		}
		for(int i=0;i<N;i++){
			if(cnt[i]==1){
				v.push_back(i);
				rv[i]=0;
				break;
			}
		}
		dfs3(v[0],200005);
		build1(0,N-1,1);
		build2(0,N-1,1);
		for(int i=0;i<S.size();i++){
			int s=rv[S[i]],e=rv[E[i]],l=L[i],r=R[i];
			bool b=false;
			if(s<e){
				b=true;
			}
			int x=bsearch1(s,e,l,b);
			int y=bsearch2(s,e,r,b);
			if(b){
				x--;
				y++;
			}
			else{
				x++;
				y--;
			}
			if(b^(x>=y)){
				ans.push_back(0);
			}
			else{
				ans.push_back(1);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<L.size();i++){
               ~^~~~~~~~~
werewolf.cpp:164:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<X.size();j++){
                ~^~~~~~~~~
werewolf.cpp:186:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<X.size();i++){
               ~^~~~~~~~~
werewolf.cpp:202:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<S.size();i++){
               ~^~~~~~~~~

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