Submission #421479

#	Time	Username	Problem	Language	Result	Execution time	Memory
421479		alireza_kaviani	Werewolf (IOI18_werewolf)	C++11	100 / 100	1032 ms	196008 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 4e5 + 10;

int nodeInd , timer , par[MAXN] , sz[MAXN] , root[MAXN] , subtree[MAXN] , st[MAXN] , fn[MAXN] , l[MAXN] , r[MAXN];
vector<int> ans , G[2][MAXN] , adj[MAXN] , Q[2][MAXN] , vec[MAXN];
set<int> sub[MAXN];

void clear(int n){
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	fill(adj , adj + MAXN , vector<int>());
	fill(subtree , subtree + MAXN , 0);
	for(int i = 0 ; i < MAXN ; i++)	root[i] = i;
	nodeInd = n;
}

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v; sz[v] += sz[u];
	adj[nodeInd].push_back(root[v]);
	adj[nodeInd].push_back(root[u]);
	root[v] = nodeInd++;
}

void PreDFS(int v){
	st[v] = ++timer;
	for(int u : adj[v]){
		PreDFS(u);
	}
	fn[v] = timer;
}

void SolveDFS(int v){
	int leaf = 1;
	for(int u : adj[v]){
		leaf = 0;
		SolveDFS(u);
		if(sub[v].size() < sub[u].size()){
			sub[v].swap(sub[u]);
		}
		for(auto &i : sub[u])	sub[v].insert(i);
	}
	if(leaf)	sub[v].insert(st[v]);
	for(int i : vec[v]){
		auto it = sub[v].lower_bound(l[i]);
		if(it == sub[v].end() || (*it) > r[i])	ans[i] = 0;
	}
}

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 m = X.size() , q = S.size();
	ans = vector<int>(q , 1);
	for(int i = 0 ; i < m ; i++){
		int v = X[i] , u = Y[i];
		if(v > u)	swap(v , u);
		G[0][v].push_back(u);
		G[1][u].push_back(v);
	}
	for(int i = 0 ; i < q ; i++){
		Q[0][L[i]].push_back(i);
		Q[1][R[i]].push_back(i);
	}
	clear(n);
	for(int i = n - 1 ; i >= 0 ; i--){
		for(int j : G[0][i]){
			Union(i , j);
		}
		for(int j : Q[0][i]){
			if(S[j] < i)	ans[j] = 0;
			subtree[j] = root[Find(S[j])];
		}
	}
	PreDFS(nodeInd - 1);
	for(int i = 0 ; i < q ; i++){
		l[i] = st[subtree[i]];
		r[i] = fn[subtree[i]];
	}
	clear(n);
	for(int i = 0 ; i < n ; i++){
		for(int j : G[1][i]){
			Union(i , j);
		}
		for(int j : Q[1][i]){
			if(E[j] > i)	ans[j] = 0;
			subtree[j] = root[Find(E[j])];
			vec[subtree[j]].push_back(j);
		}
	}
	SolveDFS(nodeInd - 1);
	return ans;
}

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