Submission #132054

#	Time	Username	Problem	Language	Result	Execution time	Memory
132054		dvdg6566	Werewolf (IOI18_werewolf)	C++14	0 / 100	2921 ms	59640 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi>vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define MAXN 200100

vi V[MAXN];
int N,M,Q,a,b;
bool A[MAXN][2];
int pos[MAXN], val[MAXN];
int vis[MAXN];

struct node{
	int s,e,m,lv,rv;
	node *l,*r;
	node(int _s,int _e):s(_s),e(_e){
		m=(s+e)/2;
		lv=MAXN;rv=0;
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			lv = min(r->lv,l->lv);
			rv = max(r->rv,l->rv);
		}else{
			lv=rv=val[s];
		}
	}
	void db(){
		cout<<s<<' '<<e<<' '<<lv<<' '<<rv<<'\n';
		if (s!=e){
			l->db();r->db();
		}
	}
	int rangemax(int x, int y){
		if (s==x&&e==y)return rv;
		if (y <= m)return l->rangemax(x,y);
		else if (x > m)return r->rangemax(x,y);
		return max(l->rangemax(x,m), r->rangemax(m+1,y));
	}
	int rangemin(int x, int y){
		if (s==x&&e==y)return lv;
		if (y <= m)return l->rangemin(x,y);
		else if (x > m)return r->rangemin(x,y);
		return min(l->rangemin(x,m), r->rangemin(m+1,y));
	}
}*root;

void dfs(int x, int p){
	pos[x] = a++;
	val[pos[x]] = x;
	for (auto v:V[x])if (v!=p){
		dfs(v,x);
	}
}

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) {
	Q = SZ(S);M=SZ(X);
	for (int i=0;i<M;++i){
		a=X[i];b=Y[i];
		V[a].pb(b);
		V[b].pb(a);
	}
	a=1;
	int rt = 0;
	while (SZ(V[rt]) == 2)++rt;
	dfs(rt,0);

	// for (int i=0;i<N;++i)cout<<pos[i]<<' ';cout<<'\n';

	root = new node(1,N);
	
	// root->db();

	vi out(Q,0);
	for (int i=0;i<Q;++i){
		if (pos[S[i]] < pos[E[i]]){
			int a = pos[S[i]];
			// Find the furthest node
			int s=a;
			int e=N;
			while (e-s>1){
				// cout<<"R "<<s<<' '<<e<<'\n';
				int m=(s+e)/2;
				// cout<<"Query "<<a<<' '<<m<<' '<<root->rangemin(a,m)<<'\n';
				if (root->rangemin(a, m)<L[i])e=m-1;
				else s=m;
			}
			// cout<<"R "<<s<<' '<<e<<'\n';
			if (root->rangemin(a,e) < L[i])--e;
			int b = e;
			// cout<<a<<' '<<b<<'\n';

			a =pos[E[i]];
			s=1;
			e=a;
			while (e-s>1){
				int m=(s+e)/2;
				// cout<<m<<' '<<a<<' '<<root->rangemin(m,a)<<'\n';	
				if (root->rangemax(m,a)>R[i])s=m+1;
				else e=m;
			}
			// cout<<s<<' '<<e<<'\n';
			if (root->rangemax(s,a) > R[i])++s;
			if (b >= s)out[i]=1;
		}else{
			swap(S[i],E[i]);
			// cout<<pos[S[i]]<<' '<<pos[E[i]]<<'\n';
			int a = pos[S[i]];
			// Find the furthest node
			int s=a;
			int e=N;
			while (e-s>1){
				// cout<<"R "<<s<<' '<<e<<'\n';
				int m=(s+e)/2;
				// cout<<"Query "<<a<<' '<<m<<' '<<root->rangemin(a,m)<<'\n';
				if (root->rangemin(a, m)>R[i])e=m-1;
				else s=m;
			}
			// cout<<"R "<<s<<' '<<e<<'\n';
			if (root->rangemin(a,e) >R[i])--e;
			int b = e;
			// cout<<a<<' '<<b<<'\n';

			a =pos[E[i]];
			s=1;
			e=a;
			while (e-s>1){
				int m=(s+e)/2;
				// cout<<m<<' '<<a<<' '<<root->rangemin(m,a)<<'\n';	
				if (root->rangemax(m,a)<L[i])s=m+1;
				else e=m;
			}
			// cout<<s<<' '<<e<<'\n';
			if (root->rangemin(s,a) < L[i])++s;
			if (b >= s)out[i]=1;
		}
	}
  	return out;
}

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