Submission #88842

#	Time	Username	Problem	Language	Result	Execution time	Memory
88842		dsjong	Werewolf (IOI18_werewolf)	C++14	15 / 100	1424 ms	140980 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 st1[200001][19];
int st2[200001][19];
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 N){
	for(int i=0;i<N;i++){
		st1[i][0]=i;
	}
	for(int j=1;j<=(int)log2(N);j++){
		for(int i=0;i<N+1-(1<<j);i++){
			if(v[st1[i][j-1]]<v[st1[i+(1<<(j-1))][j-1]]){
				st1[i][j]=st1[i][j-1];
			}
			else{
				st1[i][j]=st1[i+(1<<(j-1))][j-1];
			}
		}
	}
}
void build2(int N){
	for(int i=0;i<N;i++){
		st2[i][0]=i;
	}
	for(int j=1;j<=(int)log2(N);j++){
		for(int i=0;i<N+1-(1<<j);i++){
			if(v[st2[i][j-1]]>v[st2[i+(1<<(j-1))][j-1]]){
				st2[i][j]=st2[i][j-1];
			}
			else{
				st2[i][j]=st2[i+(1<<(j-1))][j-1];
			}
		}
	}
}
int query1(int L,int R){
	int j=(int)log2(R-L+1);
	if(v[st1[L][j]]<v[st1[R-(1<<j)+1][j]]){
		return st1[L][j];
	}
	return st1[R-(1<<j)+1][j];
}
int query2(int L,int R){
	int j=(int)log2(R-L+1);
	if(v[st2[L][j]]>v[st2[R-(1<<j)+1][j]]){
		return st2[L][j];
	}
	return st2[R-(1<<j)+1][j];
}
int bsearch1(int s,int e,int l,bool b){
	if(v[query1(s,e)]>=l){
		if(b) return e+1;
		return e-1;
	}
	if(b){
		//search from left
		int m=(s+e)/2;
		if(e-s<=1){
			if(v[s]<l){
				return s;
			}
			return e;
		}
		if(v[query1(s,m)]<l){
			return bsearch1(s,m,l,b);
		}
		return bsearch1(m,e,l,b);
	}
	else{
		//search from right
		int m=(s+e)/2;
		if(s-e<=1){
			if(v[s]<l){
				return s;
			}
			return e;
		}
		if(v[query1(m,s)]<l){
			return bsearch1(m,s,l,b);
		}
		return bsearch1(e,m,l,b);
	}
}
int bsearch2(int s,int e,int r,bool b){
	if(v[query2(s,e)]<=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(v[query2(m,e)]>r){
			return bsearch2(m,e,r,b);
		}
		return bsearch2(s,m,r,b);
	}
	else{
		//search from left
		int m=(s+e)/2;
		if(s-e<=1){
			if(v[e]>r){
				return e;
			}
			return s;
		}
		if(v[query2(e,m)]>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(N);
		build2(N);
		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:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<L.size();i++){
               ~^~~~~~~~~
werewolf.cpp:171:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<X.size();j++){
                ~^~~~~~~~~
werewolf.cpp:193:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<X.size();i++){
               ~^~~~~~~~~
werewolf.cpp:209: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