Submission #1034628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034628		vjudge1	Werewolf (IOI18_werewolf)	C++17	0 / 100	4057 ms	44652 KiB

werewolf

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

const int INF = 1e9+7;

struct STreeMin{
	ll n;
	vector<ll> st;
	STreeMin(ll n) : n(n), st(4*n+5,INF) {}
	void upd(ll k, ll l, ll r, ll p, ll v){
		if(l+1==r){ st[k]=v; return;}
		ll mid = (l+r)/2;
		if(mid>p) upd(2*k,l,mid,p,v);
		else upd(2*k+1,mid,r,p,v);
		st[k]=min(st[2*k],st[2*k+1]);
	}
	ll query(ll k, ll l, ll r, ll L, ll R){
		if(l>=R||r<=L) return INF;
		if(l>=L && r<=R) return st[k];
		ll mid = (l+r)/2;
		return min(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
	}
	void upd(ll p, ll v){upd(1,0,n,p,v);}
	ll query(ll l, ll r){return query(1,0,n,l,r);}
};

struct STreeMax{
	ll n;
	vector<ll> st;
	STreeMax(ll n) : n(n), st(4*n+5,0) {}
	void upd(ll k, ll l, ll r, ll p, ll v){
		if(l+1==r){ st[k]=v; return;}
		ll mid = (l+r)/2;
		if(mid>p) upd(2*k,l,mid,p,v);
		else upd(2*k+1,mid,r,p,v);
		st[k]=max(st[2*k],st[2*k+1]);
	}
	ll query(ll k, ll l, ll r, ll L, ll R){
		if(l>=R||r<=L) return 0;
		if(l>=L && r<=R) return st[k];
		ll mid = (l+r)/2;
		return max(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
	}
	void upd(ll p, ll v){upd(1,0,n,p,v);}
	ll query(ll l, ll r){return query(1,0,n,l,r);}
};



#include "werewolf.h"

const int MAXN = 200000+5;

ll level[MAXN];
vector<ll> adj[MAXN];

ll orden[MAXN];

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) {
	forn(i,0,SZ(X)){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	
	ll iNode = -1;
	for(int i = N-1; i >=0; i--){
		if(SZ(adj[i])==1){ iNode=i; break; }
	}
	level[iNode]=0;
	orden[0]=iNode;
	ll nd = adj[iNode][0];
	ll parent = iNode;
	while(true){
		level[nd]=level[parent]+1;
		orden[level[nd]]=nd;
		//cout<<nd<<" "<<level[nd]<<" "<<parent<<'\n';
		if(SZ(adj[nd])==1) break;
		ll p = nd;
		nd = (parent!=adj[nd][0] ? adj[nd][0] : adj[nd][1] );
		parent = p;
	}
	
	STreeMin stmin(N);
	STreeMax stmax(N);
	
	forn(i,0,N){
		stmin.upd(i,orden[i]);
		stmax.upd(i,orden[i]);
	}
	
	vector<int> res;
	
	ll l,r;
	ll u,v;  // u to v
	forn(i,0,SZ(S)){
		u=min(level[S[i]],level[E[i]]);
		v=min(level[S[i]],level[E[i]]);

		///////////////////////////////////
		//forn(j,0,N) cout<<stmin.query(j,j+1)<<" "; cout<<'\n';
		///////////////////////////////////
		
		forn(j,L[i],R[i]+1){
			stmin.upd(level[j],INF);
		}
		forn(j,L[i],R[i]+1){
			stmax.upd(level[j],0);
		}
		
		///////////////////////////////////
		//forn(j,0,N) cout<<stmin.query(j,j+1)<<" "; cout<<'\n';
		///////////////////////////////////
		
		l = 0; r = N;
		while(l<=r){
			ll mid = (l+r)/2;
			//cout<<mid<<" -> "<<stmin.query(u,min(u+mid,(ll)N-1)+1)<<'\n';
			if(stmin.query(u,min(u+mid,(ll)N-1)+1)>R[i]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		ll Left = min(u+r,(ll)N-1);
		
		l = 0; r = N;
		while(l<=r){
			ll mid = (l+r)/2;
			if(stmax.query(max((ll)0,v-mid),v+1)<L[i]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		ll Right = max((ll)0,v-r);
		
		//cout<<Left<<" "<<Right<<'\n';
		if(Left>=Right) res.pb(1);
		else res.pb(0);
		
	}
	return res;
}

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