Submission #114925

#	Time	Username	Problem	Language	Result	Execution time	Memory
114925		dsjong	Werewolf (IOI18_werewolf)	C++14	0 / 100	500 ms	524288 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) continue;
		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<20;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){
	int k=log2(r-l+1);
	//if(t==1) cout<<"QUERY MIN "<<l<<" "<<r<<" "<<min(st1[l][k],st1[r-(1<<k)+1][k])<<endl;
	//else cout<<"QUERY MAX "<<l<<" "<<r<<" "<<max(st2[l][k],st2[r-(1<<k)+1][k])<<endl;
	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,r,2);
	if(q1>=l&&q2<=r) return 0;	//GOOD
	if(q1>=l&&q2>r) return 1;	//MOVE RIGHT
	if(q1<l&&q2<=r) return 2;	//MOVE LEFT
	if(q1<l&&q2>r) return 3;	//BAD
}
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]);
	}
	dfs(0,-1,1);
	dfs(last,-1,2);
	vector<int>ans;
	/*for(int i=0;i<N;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;*/
	build();
	for(int i=0;i<S.size();i++){
		int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
		if(s>e) swap(s,e);
		int ll=s,rr=e;
		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)){
			ans.push_back(1);
		}
		else ans.push_back(0);
		hell:;
	}
	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:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<S.size();i++){
              ~^~~~~~~~~
werewolf.cpp: In function 'int check(int, int, int, int, int)':
werewolf.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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