Submission #1047180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047180		Alihan_8	Werewolf (IOI18_werewolf)	C++17	15 / 100	4054 ms	63488 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, _in, _out, euler;
	
	vector <vector<int>> adj;
	
	bool isMax;
	
	Dsu(int n, bool isMax) : isMax(isMax) {
		fa.resize(n);
		iota(all(fa), 0);
		
		adj.resize(n);
		_in.resize(n);
		_out.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{
			_in[u] = ++ct;
			euler.pb(u);
			
			for ( auto &v: adj[u] ){
				//~ cout << u << " " << v << ln;
				
				dfs(dfs, v);
			} _out[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 <int> ans(q);
	
	for ( int i = 0; i < q; i++ ){
		for ( int j = ds._in[ps[i]]; j <= ds._out[ps[i]]; j++ ){ // subtree of pe[i]
			for ( int k = de._in[pe[i]]; k <= de._out[pe[i]]; k++ ){ // subtree of pe[i]
				if ( ds.euler[j] == de.euler[k] ){
					ans[i] = 1;
				}
			}
		}
	}
	
	return ans;
}

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