Submission #115020

#	Time	Username	Problem	Language	Result	Execution time	Memory
115020		dsjong	Werewolf (IOI18_werewolf)	C++14	34 / 100	752 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) 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
}
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;
	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;
}

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:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<S.size();i++){
              ~^~~~~~~~~

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