Submission #1047189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047189		Alihan_8	Werewolf (IOI18_werewolf)	C++17	100 / 100	440 ms	103872 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'

struct Dsu{
	vector <int> fa, tin, tout, euler;
	
	vector <vector<int>> adj;
	
	bool isMax;
	
	Dsu(int n, bool isMax) : isMax(isMax) {
		fa.resize(n);
		iota(all(fa), 0);
		
		adj.resize(n);
		tin.resize(n);
		tout.resize(n);
	}
	
	int get(int u){
		return u ^ fa[u] ? fa[u] = get(fa[u]) : u;
	}
	
	bool f(int u, int v){
		return isMax ? u > v : u < v;
	}
	
	bool merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return false;
		
		if ( !f(u, v) ) swap(u, v);
		
		fa[v] = u; 
		adj[u].pb(v);
		
		return true;
	}
	
	void RunDfs(){
		int ct = -1;
		
		auto dfs = [&](auto dfs, int u) -> void{
			tin[u] = ++ct;
			euler.pb(u);
			
			for ( auto &v: adj[u] ){
				//~ cout << u << " " << v << ln;
				
				dfs(dfs, v);
			} tout[u] = ct;
		};
		
		int root = get(0);
		
		dfs(dfs, root);
	}
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int n = N, m = X.size(), q = S.size();
	
	// Subtask #3
	
	vector <vector<int>> adj(n);
	
	for ( int i = 0; i < m; i++ ){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	
	Dsu ds(n, 0), de(n, 1);
	
	vector <int> ps(q), pe(q);

	{ // for S[i]
		vector <vector<int>> qu(n);
		
		for ( int i = 0; i < q; i++ ){
			qu[L[i]].pb(i);
		}
		
		for ( int u = n - 1; u >= 0; u-- ){
			for ( auto &v: adj[u] ){
				if ( v > u ){
					ds.merge(u, v);
				}
			}
			
			for ( auto &j: qu[u] ){
				ps[j] = ds.get(S[j]);
			}
		}
	}
	{ // for E[i]
		vector <vector<int>> qu(n);
		
		for ( int i = 0; i < q; i++ ){
			qu[R[i]].pb(i);
		}
		
		for ( int u = 0; u < n; u++ ){
			for ( auto &v: adj[u] ){
				if ( v < u ){
					de.merge(u, v);
				}
			}
			
			for ( auto &j: qu[u] ){
				pe[j] = de.get(E[j]);
			}
		}
	}
	
	ds.RunDfs(); 
	de.RunDfs(); 
	
	vector <vector<int>> qu(n);
	
	for ( int i = 0; i < q; i++ ){
		qu[ps[i]].pb(i);
	}
	
	vector <set<int>> s(n);
	
	vector <int> ans(q);
	
	auto dfs = [&](auto dfs, int u) -> void{
		s[u].insert(de.tin[u]);
		
		for ( auto &v: ds.adj[u] ){
			dfs(dfs, v);
			
			if ( s[u].size() < s[v].size() ){
				swap(s[u], s[v]);
			}
			
			for ( auto &x: s[v] ){
				s[u].insert(x);
			} s[v].clear();
		}
		
		for ( auto &j: qu[u] ){
			int l = de.tin[pe[j]], r = de.tout[pe[j]];
			
			ans[j] = (s[u].lower_bound(l) != s[u].upper_bound(r));
		}
	};
	
	dfs(dfs, 0);
	
	return ans;
}

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