Submission #294393

#	Time	Username	Problem	Language	Result	Execution time	Memory
294393		amiratou	Werewolf (IOI18_werewolf)	C++14	49 / 100	563 ms	35960 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define pb push_back
#define fi first
#define se second
typedef vector<int> v;
typedef pair<int,int> ii;
const int MX = 200002;
const int INF = (int)(1e9);

v vec[MX];
bool vis[MX][2];
int val[MX],id[MX],idx;
ii st[4*MX];
void build(int node,int l,int r){
	if(l==r){
		st[node]={val[l],val[l]};
		return;
	}
	int med=(l+r)>>1;
	build(node*2,l,med),build(node*2+1,med+1,r);
	st[node]={min(st[node*2].fi,st[node*2+1].fi),max(st[node*2].se,st[node*2+1].se)};
}
ii query(int node,int l,int r,int i,int j){
	if(l>j || r<i)
		return {INF,-1};
	if(l>=i && r<=j)return st[node];
	int med=(l+r)>>1;
	ii q=query(node*2,l,med,i,j),q2=query(node*2+1,med+1,r,i,j);
	return {min(q.fi,q2.fi),max(q.se,q2.se)};
}
int gimme_r(int node,int l,int r,int i,int j,int R){
	if(l>j || r<i)return -1;
	if(l>=i && r<=j){
		if(st[node].se<=R)return -1;
		while(l!=r){
			int med=(l+r)>>1;
			if(st[node*2+1].se>R)
				l=med+1,node=node*2+1;
			else r=med,node*=2;
		}
		return l;
	}
	int med=(l+r)>>1;
	int q=gimme_r(node*2+1,med+1,r,i,j,R);
	if(q!=-1)return q;
	return gimme_r(node*2,l,med,i,j,R);
}
int gimme_l(int node,int l,int r,int i,int j,int R){
	if(l>j || r<i)return -1;
	if(l>=i && r<=j){
		if(st[node].se<=R)return -1;
		while(l!=r){
			int med=(l+r)>>1;
			if(st[node*2].se>R)
				r=med,node*=2;
			else l=med+1,node=node*2+1; 
		}
		return l;
	}
	int med=(l+r)>>1;
	int q=gimme_l(node*2,l,med,i,j,R);
	if(q!=-1)return q;
	return gimme_l(node*2+1,med+1,r,i,j,R);
}

vector<int> check_validity(int N, v X, v Y,v S, v E,v L, v R) {
	int Q = sz(S);
	v A(Q);
	for (int i = 0; i < sz(X); ++i)
	{
		vec[X[i]].pb(Y[i]);
		vec[Y[i]].pb(X[i]);
	}
	if(N<=3000){
		for (int i = 0; i < Q; ++i)
		{
			if(i)for (int j = 0; j < N; ++j)
				vis[j][0]=vis[j][1]=0;
			queue<ii> q;
			q.push({S[i],0});
			vis[S[i]][0]=1;
			while(!q.empty()){
				ii f=q.front();
				q.pop();
				if(f.fi==E[i]){
					if(f.se || ((S[i]>=L[i]) && (S[i]<=R[i]))){
						A[i]=1;break;
					}
				}
				if(f.fi>R[i])assert(!f.se);
				if(f.fi<L[i])assert(f.se);
				if((!f.se) && (f.fi>=L[i]) && (f.fi<=R[i]) && !vis[f.fi][1]){
					vis[f.fi][1]=1;
					q.push({f.fi,1});
				}
				for(auto it:vec[f.fi]){
					if(vis[it][f.se])continue;
					if((!f.se && it>=L[i]) || (f.se && it<=R[i])){
						vis[it][f.se]=1;
						q.push({it,f.se});
					}
				}
			}
		}
	}
	else{
		int node=-1,p=-1,a;
		ii h;
		for (int i = 0; i < N; ++i)
			if(sz(vec[i])==1){
				node=i;
				break;
			}
		assert(node!=-1);
		while(1){
			id[node]=idx,val[idx++]=node;
			int cnt=0;
			for(auto it:vec[node])
				if(it!=p){p=node,node=it,cnt++;break;}
			if(!cnt)break;
		}
		build(1,0,N-1);
		for (int i = 0; i < Q; ++i)
		{
			if(id[S[i]]<id[E[i]]){
				a=gimme_r(1,0,N-1,id[S[i]],id[E[i]],R[i]);
				if((a==-1) && (S[i]>=L[i]))A[i]=1;
				else if(a!=-1 && a!=id[E[i]]){
					assert(val[a]>R[i]);
					h=query(1,0,N-1,id[S[i]],a);
					if((h.fi>=L[i]) && (val[a+1]>=L[i]))A[i]=1;
				}
			}
			else{
				a=gimme_l(1,0,N-1,id[E[i]],id[S[i]],R[i]);
				if((a==-1) && (S[i]>=L[i]))A[i]=1;
				else if(a!=-1 && a!=id[E[i]]){
					assert(val[a]>R[i]);
					h=query(1,0,N-1,a,id[S[i]]);
					if((h.fi>=L[i]) && (val[a-1]>=L[i]))A[i]=1;
				}
			}
		}
	}
	return A;
}

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