Submission #115024

#	Time	Username	Problem	Language	Result	Execution time	Memory
115024		dsjong	Werewolf (IOI18_werewolf)	C++14	49 / 100	703 ms	64396 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj[200005];
int a[200005],pos[200005];
int last=0,cnt=0;
void dfs(int i,int p,int t){
	pos[i]=cnt;
	if(t==2) a[cnt++]=i;
	last=i;
	for(int j:adj[i]){
		if(j!=p) dfs(j,i,t);
	}
}
int st1[200005][20],st2[200005][20];
void build(){
	for(int i=0;i<cnt;i++){
		st1[i][0]=st2[i][0]=a[i];
	}
	for(int j=1;j<19;j++){
		for(int i=0;i<=cnt-(1<<j);i++){
			st1[i][j]=min(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
			st2[i][j]=max(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r,int t){
	if(l>r) swap(l,r);
	int k=log2(r-l+1);
	if(t==1) return min(st1[l][k],st1[r-(1<<k)+1][k]);
	else return max(st2[l][k],st2[r-(1<<k)+1][k]);
}
int check(int s,int e,int m,int l,int r){
	int q1=query(s,m,1),q2=query(m,e,2);
	if(q1>=l&&q2<=r) return 0;	//GOOD
	else if(q1>=l) return 1;	//MOVE RIGHT
	else if(q2<=r) return 2;	//MOVE LEFT
	else return 3;				//BAD
}
bool vis[3005][3];
void dfs2(int i,int m,int t){
	vis[i][t]=true;
	for(int j:adj[i]){
		if(vis[j][t]) continue;
		if(t==1&&j<m) continue;
		if(t==2&&j>m) continue;
		dfs2(j,m,t);
	}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	for(int i=0;i<X.size();i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	if(N>3000){
		dfs(0,-1,1);
		dfs(last,-1,2);
		vector<int>ans;
		build();
		for(int i=0;i<S.size();i++){
			int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
			int ll=s,rr=e;
			if(s<e){
				while(ll<rr){
					int mm=(ll+rr)/2;
					//cout<<mm<<" ";
					int ch=check(s,e,mm,l,r);
					if(ch==0){
						ans.push_back(1);
						goto hell;
					}
					else if(ch==3){
						ans.push_back(0);
						goto hell;
					}
					else if(ch==1) ll=mm+1;
					else rr=mm-1;
					if(ll>rr){
						ans.push_back(0);
						goto hell;
					}
				}
			}
			else{
				while(ll>rr){
					int mm=(ll+rr)/2;
					int ch=check(s,e,mm,l,r);
					if(ch==0){
						ans.push_back(1);
						goto hell;
					}
					else if(ch==3){
						ans.push_back(0);
						goto hell;
					}
					else if(ch==1) ll=mm-1;
					else rr=mm+1;
					if(ll<rr){
						ans.push_back(0);
						goto hell;
					}
				}
			}
			if(check(s,e,ll,l,r)==0){
				ans.push_back(1);
			}
			else ans.push_back(0);
			hell:;
		}
		return ans;
	}
	else{
		vector<int>ans;
		for(int i=0;i<S.size();i++){
			int s=S[i],e=E[i],l=L[i],r=R[i];
			memset(vis,false,sizeof vis);
			dfs2(s,l,1);
			dfs2(e,r,2);
			for(int j=l;j<=r;j++){
				if(vis[j][1]&&vis[j][2]){
					ans.push_back(1);
					goto hell2;
				}
			}
			ans.push_back(0);
			hell2:;
		}
		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:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<S.size();i++){
               ~^~~~~~~~~
werewolf.cpp:114: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: 34 / 34
• Subtask 4: 0 / 51