Submission #765922

#	Time	Username	Problem	Language	Result	Execution time	Memory
765922		sentheta	Werewolf (IOI18_werewolf)	C++17	34 / 100	490 ms	69860 KiB

werewolf

#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 2e5+5;
const int LN = 18;

int n, m, q;
V<int> adj[N];

V<int> ans;

int a[N];
struct Stable{
	int mn[N][LN], mx[N][LN];
	void build(){
		rep(i,0,N) mn[i][0] = mx[i][0] = a[i];
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<N; i++){
			mn[i][lg] = min(mn[i][lg-1], mn[i+(1<<(lg-1))][lg-1]);
			mx[i][lg] = max(mx[i][lg-1], mx[i+(1<<(lg-1))][lg-1]);
		}
	}
	int qryMin(int l,int r){
		int lg = __lg(r-l+1);
		return min(mn[l][lg], mn[r-(1<<lg)+1][lg]);
	}
	int qryMax(int l,int r){
		int lg = __lg(r-l+1);
		return max(mx[l][lg], mx[r-(1<<lg)+1][lg]);
	}
} stable;


int ord[N];
void dfs_ord(int x){
	a[ord[x]] = x;
	for(int y : adj[x]) if(ord[y]==-1){
		ord[y] = ord[x]+1;
		dfs_ord(y);
	}
}

V<int> check_validity(int _n,V<int>_u,V<int>_v,
							V<int>_s,V<int>_e,V<int>_l,V<int>_r){
	n=_n; m=_u.size(); q=_s.size();
	ans = V<int>(q);

	rep(i,0,m){
		adj[_u[i]].push_back(_v[i]);
		adj[_v[i]].push_back(_u[i]);
	}

	rep(i,0,n) ord[i] = -1;
	rep(i,0,n) if(adj[i].size()==1){
		ord[i] = 0;
		dfs_ord(i);
		break;
	}
	stable.build();
	// rep(i,0,n) cout << a[i] << " ";
	// cout << nl;

	rep(i,0,q){
		int s = _s[i], e = _e[i];
		int l = _l[i], r = _r[i];

		int si = ord[s], ei = ord[e];
		// dbg(si); dbg(ei);

		if(si < ei){
			int p = si, q = ei;
			for(int J=1<<LN; J; J/=2){
				if(p+J<=ei && stable.qryMin(si,p+J)>=l) p+=J;
				if(q-J>=si && stable.qryMax(q-J,ei)<=r) q-=J;
			}
			// dbg(p); dbg(q);
			ans[i] = q<=p;
		}

		if(ei < si){
			int p = ei, q = si;
			for(int J=1<<LN; J; J/=2){
				if(p+J<=si && stable.qryMax(ei,p+J)<=r) p+=J;
				if(q-J>=ei && stable.qryMin(q-J,si)>=l) q-=J;
			}
			ans[i] = q<=p;
		}
	}

	return ans;
}

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