oj.uz

Submission #422146

# Submission time Handle Problem Language Result Execution time Memory
422146 2021-06-09T18:53:18 Z MohamedAhmed04 Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 113964 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) ;
		s[child].clear() ;
	}
	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 22 ms 28572 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 19 ms 28488 KB Output is correct
4 Correct 18 ms 28504 KB Output is correct
5 Correct 19 ms 28512 KB Output is correct
6 Correct 18 ms 28572 KB Output is correct
7 Correct 20 ms 28504 KB Output is correct
8 Correct 19 ms 28508 KB Output is correct
9 Correct 19 ms 28544 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28572 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 19 ms 28488 KB Output is correct
4 Correct 18 ms 28504 KB Output is correct
5 Correct 19 ms 28512 KB Output is correct
6 Correct 18 ms 28572 KB Output is correct
7 Correct 20 ms 28504 KB Output is correct
8 Correct 19 ms 28508 KB Output is correct
9 Correct 19 ms 28544 KB Output is correct
10 Correct 89 ms 29888 KB Output is correct
11 Correct 57 ms 29816 KB Output is correct
12 Correct 24 ms 29736 KB Output is correct
13 Correct 50 ms 29920 KB Output is correct
14 Correct 27 ms 29872 KB Output is correct
15 Correct 34 ms 29900 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1226 ms 113964 KB Output is correct
2 Execution timed out 4098 ms 108132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28572 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 19 ms 28488 KB Output is correct
4 Correct 18 ms 28504 KB Output is correct
5 Correct 19 ms 28512 KB Output is correct
6 Correct 18 ms 28572 KB Output is correct
7 Correct 20 ms 28504 KB Output is correct
8 Correct 19 ms 28508 KB Output is correct
9 Correct 19 ms 28544 KB Output is correct
10 Correct 89 ms 29888 KB Output is correct
11 Correct 57 ms 29816 KB Output is correct
12 Correct 24 ms 29736 KB Output is correct
13 Correct 50 ms 29920 KB Output is correct
14 Correct 27 ms 29872 KB Output is correct
15 Correct 34 ms 29900 KB Output is correct
16 Correct 1226 ms 113964 KB Output is correct
17 Execution timed out 4098 ms 108132 KB Time limit exceeded
18 Halted 0 ms 0 KB -