Submission #422144

#	Time	Username	Problem	Language	Result	Execution time	Memory
422144		MohamedAhmed04	Werewolf (IOI18_werewolf)	C++14	15 / 100	2267 ms	524292 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"

using namespace std ;

const int MAX = 2e5 + 10 ;

int n , m , q ;

int par[MAX] ;
int par2[MAX] ;

int P[MAX][20] , P2[MAX][20] ;

vector< vector<int> >adj(MAX) , adj1(MAX) , adj2(MAX) ;

void init()
{
	for(int i = 1 ; i <= n ; ++i)
		par[i] = par2[i] = i ;
}


int root(int node)
{
	if(par[node] == node)
		return node ;
	return (par[node] = root(par[node])) ;
}

void Union(int x , int y)
{
	int a = root(x) ;
	int b = root(y) ;
	if(a < b)
		swap(a , b) ;
	par[b] = a , P[b][0] = a ;
	adj1[a].push_back(b) ;
}

int root2(int node)
{
	if(par2[node] == node)
		return node ;
	return (par2[node] = root2(par2[node])) ;
}

void Union2(int x , int y)
{
	int a = root2(x) ;
	int b = root2(y) ;
	if(a > b)
		swap(a , b) ;
	par2[b] = a , P2[b][0] = a ;
	adj2[a].push_back(b) ;
}

int in[MAX] , out[MAX] ;
int tim = 0 ;

void dfs1(int node)
{
	in[node] = ++tim ;
	for(int j = 1 ; j < 18 ; ++j)
		P[node][j] = P[P[node][j-1]][j-1] ;
	for(auto &child : adj1[node])
		dfs1(child) ;
	out[node] = tim ;
}

int sz[MAX] ;

void dfs2(int node)
{
	for(int j = 1 ; j < 18 ; ++j)
		P2[node][j] = P2[P2[node][j-1]][j-1] ;
	sz[node] = 1 ;
	for(auto &child : adj2[node])
		dfs2(child) ;
}

void preprocess()
{
	init() ;
	for(int i = 0 ; i < n ; ++i)
	{
		for(auto &child : adj[i])
		{
			if(child < i && root(child) != root(i))
				Union(child , i) ;
		}
	}
	for(int i = n-1 ; i >= 0 ; --i)
	{
		for(auto &child : adj[i])
		{
			if(child > i && root2(child) != root2(i))
				Union2(child , i) ;
		}
	}
	P[n-1][0] = n-1 ;
	dfs1(n-1) ;
	dfs2(0) ;
}

int get(int node , int node2)
{
	for(int j = 17 ; j >= 0 ; --j)
	{
		if(P[node][j] <= node2)
			node = P[node][j] ;
	}
	return node ;
}

int get2(int node , int node2)
{
	for(int j = 17 ; j >= 0 ; --j)
	{
		if(P2[node][j] >= node2)
			node = P2[node][j] ;
	}
	return node ;
}

set<int>s[MAX] ;
vector< pair<int , int> >queries[MAX] ;
vector<int>ans ;

void dfs3(int node)
{
	int big = -1 , bigchild = -1 ;
	for(auto &child : adj2[node])
	{
		if(sz[child] > big)
			big = sz[child] , bigchild = child ;
	}
	for(auto &child : adj2[node])
		dfs3(child) ;
	if(bigchild != -1)
		swap(s[node] , s[bigchild]) ;
	s[node].insert(in[node]) ;
	for(auto &child : adj2[node])
	{
		if(child == bigchild)
			continue ;
		for(auto &i : s[child])
			s[node].insert(i) ;
	}
	for(auto &p : queries[node])
	{
		int l = in[p.first] , r = out[p.first] ;
		auto it = s[node].lower_bound(l) ;
		if(it == s[node].end())
			ans[p.second] = 0 ;
		else if((*it) > r)
			ans[p.second] = 0 ;
		else
			ans[p.second] = 1 ;
	}
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) 
{
	n = N , m = X.size() , q = S.size() ;
	for(int i = 0 ; i < m ; ++i)
		adj[X[i]].push_back(Y[i]) , adj[Y[i]].push_back(X[i]) ;
	preprocess() ;
	for(int i = 0 ; i < q ; ++i)
		queries[get2(S[i] , L[i])].emplace_back(get(E[i] , R[i]) , i) ;
	ans = vector<int>(q) ;
	dfs3(0) ;
	return ans ;
}

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