Submission #1060172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060172		ReLice	Werewolf (IOI18_werewolf)	C++17	100 / 100	493 ms	100320 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
#define ins insert
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll N=2e5+5;
const ll inf=1e9;
vector<vll> G(N);
struct dsu{
	vector<vll> g;
	vll tin, tout;
	vll p, pr;
	ll tiktak;
	ll n;
	bool inc;
	
	dsu(ll N, ll f){
		n = N;
		inc = f;
		tiktak = -1;
		
		tin.resize(n);
		tout.resize(n);
		g.resize(n);
		p.resize(n);
		
		for(ll i=0;i<n;i++) p[i] = i;
	}
	
	ll anc(ll a){
		return (p[a] == a ? a : p[a] = anc(p[a]));
	}
	
	bool f(ll a, ll b){
		return inc ? a < b : a > b;
	}
	
	bool uni(ll a, ll b){
		a = anc(a), b = anc(b);
		
		if(a == b) return false;
		
		if(f(a, b)) swap(a, b);
		
		p[b] = a;
		g[a].pb(b);
		
		return true;
	}
	
	void build(vll s, vll l){
		ll i, q = s.size();
		
		pr.resize(q);
		vector<vll> qu(n);
		
		for(i=0;i<q;i++){
			qu[l[i]].pb(i);
		}
		
		if(inc) i = 0;
		else i = n - 1;
		while(i>=0 && i<n){
			for(auto to : G[i]){
				if((inc && to < i ) || (!inc && to > i)){
					uni(to, i);
				}
			}
			
			for(auto j : qu[i]){
				pr[j] = anc(s[j]);
			}
			
			//iteration
			i += inc ? 1 : -1;
		}
	}
	
	void dfs(ll v){
		tin[v] = ++tiktak;
		
		for(auto i : g[v]) dfs(i);
		
		tout[v] = tiktak;
	}
};

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	ll i;
	ll m = X.size();
	ll q = S.size();
	
	for(i=0;i<m;i++){
		G[X[i]].pb(Y[i]);
		G[Y[i]].pb(X[i]);
	}
	
	dsu s(n, 0);
	dsu t(n, 1);
	
	s.build(S, L);
	t.build(E, R);
	
	s.dfs(0);
	t.dfs(n-1);
	
	vector<vll> qu(n);
	for(i=0;i<q;i++){
		qu[s.pr[i]].pb(i);
	}
	
	vll ans(q);
	vector<set<ll>> st(n);
	
	function<void(int)> dfs = [&](ll v){
		st[v].ins(t.tin[v]);
		for(auto i : s.g[v]){
			dfs(i);
			
			if(st[v].size() < st[i].size()) swap(st[i], st[v]);
			
			for(auto j : st[i]){
				st[v].ins(j);
			}st[i].clear();
		}
		
		for(auto i : qu[v]){
			int l = t.tin[t.pr[i]], r = t.tout[t.pr[i]];
			
			ans[i] = (st[v].lb(l) != st[v].ub(r));
		}
	};
	
	dfs(0);
	
	return ans;
}

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