oj.uz

Submission #422144

# Submission time Handle Problem Language Result Execution time Memory
422144 2021-06-09T18:51:26 Z MohamedAhmed04 Werewolf (IOI18_werewolf) C++14
15 / 100
 2267 ms 524292 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28564 KB Output is correct
2 Correct 16 ms 28496 KB Output is correct
3 Correct 16 ms 28508 KB Output is correct
4 Correct 17 ms 28492 KB Output is correct
5 Correct 16 ms 28564 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 16 ms 28492 KB Output is correct
8 Correct 16 ms 28492 KB Output is correct
9 Correct 16 ms 28500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28564 KB Output is correct
2 Correct 16 ms 28496 KB Output is correct
3 Correct 16 ms 28508 KB Output is correct
4 Correct 17 ms 28492 KB Output is correct
5 Correct 16 ms 28564 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 16 ms 28492 KB Output is correct
8 Correct 16 ms 28492 KB Output is correct
9 Correct 16 ms 28500 KB Output is correct
10 Correct 85 ms 48012 KB Output is correct
11 Correct 68 ms 42740 KB Output is correct
12 Correct 25 ms 30404 KB Output is correct
13 Correct 56 ms 39548 KB Output is correct
14 Correct 27 ms 30768 KB Output is correct
15 Correct 34 ms 33256 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 208708 KB Output is correct
2 Runtime error 2267 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28564 KB Output is correct
2 Correct 16 ms 28496 KB Output is correct
3 Correct 16 ms 28508 KB Output is correct
4 Correct 17 ms 28492 KB Output is correct
5 Correct 16 ms 28564 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 16 ms 28492 KB Output is correct
8 Correct 16 ms 28492 KB Output is correct
9 Correct 16 ms 28500 KB Output is correct
10 Correct 85 ms 48012 KB Output is correct
11 Correct 68 ms 42740 KB Output is correct
12 Correct 25 ms 30404 KB Output is correct
13 Correct 56 ms 39548 KB Output is correct
14 Correct 27 ms 30768 KB Output is correct
15 Correct 34 ms 33256 KB Output is correct
16 Correct 1137 ms 208708 KB Output is correct
17 Runtime error 2267 ms 524292 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -