Submission #424382

#	Time	Username	Problem	Language	Result	Execution time	Memory
424382		Pbezz	Werewolf (IOI18_werewolf)	C++14	34 / 100	2647 ms	50708 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;
vector<vector<ll>>adj(MAXN);
ll arr[MAXN],position[MAXN],seg[4*MAXN][2];
//seg[i][0]=min
//vector<vector<ll>>seg(4*MAXN);

void recalculate(ll node){
//seg[node].resize(0);

seg[node][0]=min(seg[2*node+1][0],seg[2*node+2][0]);

seg[node][1]=max(seg[2*node+1][1],seg[2*node+2][1]);
}

void build(ll node, ll left, ll right){

if(left==right){
seg[node][0]=arr[left];
seg[node][1]=arr[left];
}else{
ll middle=(left+right)/2;

build(2*node+1,left,middle);
build(2*node+2,middle+1,right);
recalculate(node);
}
}

ll querie(ll node, ll left, ll right, ll a, ll b, ll type){

if(a<=left&&b>=right){
return seg[node][type];
}else{

ll middle=(left+right)/2,res=0;

if(type==1){
if(a<=middle)res=max(res,querie(2*node+1,left,middle,a,b,type));
if(b>=middle+1)res=max(res,querie(2*node+2,middle+1,right,a,b,type));
}else{res=INF;
if(a<=middle)res=min(res,querie(2*node+1,left,middle,a,b,type));
if(b>=middle+1)res=min(res,querie(2*node+2,middle+1,right,a,b,type));
}
return res;
}
}

void dfs(ll node, ll p,ll pos){
arr[pos]=node;
position[node]=pos;
for(auto u:adj[node]){

if(u==p)continue;

dfs(u,node,pos+1);
}
}

std::vector<int> check_validity(int N,std::vector<int>X,std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int Q = S.size(),m=(int)X.size(), i,n=N,m1,m2;

	for(i=0;i<m;i++){
	adj[X[i]].pb(Y[i]);
	adj[Y[i]].pb(X[i]);
	}

	for(i=0;i<N;i++){
	if(adj[i].size()==1)break;
	}

	dfs(i,-1,1);

	build(0,1,n);

	int s,e,l,r; ll lo,hi,mid;
	std::vector<int> A(Q);
	for(i=0;i<Q;i++){//cout<<i<<"\n";

	s=S[i]; e=E[i]; l=L[i]; r=R[i];

	if(s<l||e>r){
	A[i]=0;
	continue;
	}
//	cout<<position[s]<<" "<<position[e]<<endl;
	if(position[s]<position[e]){//cout<<"hihi";

	//saber qual a leftmost pos com arr[pos] < l 
	hi=position[e];lo=position[s];

	if( querie(0,1,n,lo,hi,0)>=l ){//cout<<"kk ";
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,lo,mid,0)>=l ){
	lo=mid;
	}else{
	hi=mid;
	}
	}

	for(mid=lo;mid<=hi;mid++){
	if( querie(0,1,n,mid,mid,0)<l ){
	break;
	}
	}
	m1=mid-1;
	//human so pode andar entre position[e] e mid-1

	//saber qual a rightmost pos com arr[pos] > r 
	hi=position[e];lo=position[s];

	if( querie(0,1,n,lo,hi,1)<=r ){//cout<<"gaga";
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,mid,hi,1)<=r ){
	hi=mid;
	}else{
	lo=mid;
	}
	}

	for(mid=hi;mid>=lo;mid--){
	if( querie(0,1,n,mid,mid,1)>r ){
	break;
	}
	}
	m2=mid+1;

	A[i]=0;
	if(m1>=m2){
	A[i]=1;
	}
	//cout<<m1<<" "<<m2<<endl;
	}else{

	//saber qual a leftmost pos com arr[pos] > r
	lo=position[e]; hi=position[s];

	if( querie(0,1,n,lo,hi,1)<=r ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,lo,mid,1)<=r ){
	lo=mid;
	}else{
	hi=mid;
	}
	}

	for(mid=lo;mid<=hi;mid++){
	if( querie(0,1,n,mid,mid,1)>r ){
	break;
	}
	}
	m1=mid-1;
	//human so pode andar entre position[e] e mid-1


	//saber qual a rightmost pos com arr[pos] <l 
	hi=position[s];lo=position[e];

	if( querie(0,1,n,lo,hi,0)>=l ){
	A[i]=1;
	continue;
	}

	while(hi-lo>=2){
	mid = lo + (hi-lo)/2;

	if( querie(0,1,n,mid,hi,0)>=l ){
	hi=mid;
	}else{
	lo=mid;
	}

	}

	for(mid=hi;mid>=lo;mid--){
	if( querie(0,1,n,mid,mid,0)<l ){
	break;
	}
	}
	m2=mid+1;
	//human so pode andar entre position[e] e mid-1
	A[i]=0;
	if(m1>=m2){
	A[i]=1;
	}

}
}
  return A;
}

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