Submission #299677

#	Time	Username	Problem	Language	Result	Execution time	Memory
299677		TMJN	Werewolf (IOI18_werewolf)	C++17	34 / 100	564 ms	29932 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

vector<int>V[200000];
vector<int>A;
int treemin[1<<19],treemax[1<<19],B[200000];

int calcmin(int l,int r){
	int a=0xE869120;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=min({a,treemin[l],treemin[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

int calcmax(int l,int r){
	int a=0;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=max({a,treemax[l],treemax[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
	assert(X.size()==N-1);
	for(int i=0;i<N-1;i++){
		V[X[i]].push_back(Y[i]);
		V[Y[i]].push_back(X[i]);
	}
	for(int i=0;i<N;i++){
		assert(V[i].size()<=2);
	}
	for(int i=0;i<N;i++){
		if(V[i].size()==1){
			A.push_back(i);
			A.push_back(V[i][0]);
			while(V[A.back()].size()>=2){
				for(int i=0;i<2;i++){
					if(V[A.back()][i]!=A[A.size()-2]){
						A.push_back(V[A.back()][i]);
						break;
					}
				}
			}
			break;
		}
	}
	for(int i=0;i<N;i++){
		treemin[i+(1<<18)]=treemax[i+(1<<18)]=A[i];
	}
	for(int i=(1<<18)-1;i;i--){
		treemin[i]=min(treemin[i+i],treemin[i+i+1]);
		treemax[i]=max(treemax[i+i],treemax[i+i+1]);
	}
	vector<int>res;
	int Q=S.size();
	for(int i=0;i<N;i++){
		B[A[i]]=i;
	}
	for(int i=0;i<Q;i++){
		S[i]=B[S[i]];
		E[i]=B[E[i]];
	}
	for(int i=0;i<Q;i++){
		if(S[i]<E[i]){
			int l,r;
			l=S[i];
			r=E[i]+1;
			while(l+1!=r){
				int m=(l+r)/2;
				if(calcmin(S[i],m)>=L[i]){
					l=m;
				}
				else{
					r=m;
				}
			}
			if(calcmax(l,E[i])<=R[i]){
				res.push_back(1);
			}
			else{
				res.push_back(0);
			}
		}
		else{
			int l,r;
			l=E[i];
			r=S[i]+1;
			while(l+1!=r){
				int m=(l+r)/2;
				if(calcmax(E[i],m)<=R[i]){
					l=m;
				}
				else{
					r=m;
				}
			}
			if(calcmin(l,S[i])>=L[i]){
				res.push_back(1);
			}
			else{
				res.push_back(0);
			}
		}
	}
	return res;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from werewolf.cpp:2:
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:34:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  assert(X.size()==N-1);
      |         ~~~~~~~~^~~~~

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