oj.uz

Submission #417447

# Submission time Handle Problem Language Result Execution time Memory
417447 2021-06-03T17:49:37 Z MohamedAhmed04 Synchronization (JOI13_synchronization) C++17
100 / 100
 318 ms 25728 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int n , m , q ;

int in[MAX] , out[MAX] , dep[MAX] , P[MAX][17] ;

int u[MAX] , v[MAX] , mark[MAX] ;
int val[MAX] , last[MAX] ;

vector< vector<int> >adj(MAX) ;

int tim = 0 ;

int bit[MAX] ;

void add(int i , int x)
{
	for(; i <= n ; i += (i & (-i)))
		bit[i] += x ;
}

int get(int i)
{
	int sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i] ;
	return sum ;
}

void dfs(int node , int par)
{
	in[node] = ++tim ;
	P[node][0] = par ;
	for(int j = 1 ; j < 17 ; ++j)
		P[node][j] = P[P[node][j-1]][j-1] ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , node) ;
	}
	out[node] = tim ;
}

int root(int node)
{
	for(int j = 16 ; j >= 0 ; --j)
	{
		if(!P[node][j])
			continue ;
		if(get(in[P[node][j]]) + (1 << j) == get(in[node]))
			node = P[node][j] ;
	}
	return node ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>q ;
	for(int i = 1 ; i <= n-1 ; ++i)
	{
		cin>>u[i]>>v[i] ;
		adj[u[i]].push_back(v[i]) ;
		adj[v[i]].push_back(u[i]) ;
	}
	dfs(1 , 0) ;
	for(int i = 1 ; i <= n ; ++i)
		val[i] = 1 ;
	while(m--)
	{
		int idx ;
		cin>>idx ;
		int x = u[idx] , y = v[idx] ;
		if(P[x][0] == y)
			swap(x , y) ;
		if(!mark[idx])
		{
			add(in[y] , 1) ;
			add(out[y]+1 , -1) ;
			mark[idx] = 1 ;
			val[root(y)] += val[y] - last[y] ;
		}
		else
		{
			mark[idx] = 0 ;
			last[y] = val[y] = val[root(y)] ;
			add(in[y] , -1) ;
			add(out[y]+1 , 1) ;
		}
	}
	while(q--)
	{
		int node ;
		cin>>node ;
		cout<<val[root(node)]<<"\n" ;
	}
	return 0 ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 15 ms 6476 KB Output is correct
8 Correct 15 ms 6528 KB Output is correct
9 Correct 15 ms 6476 KB Output is correct
10 Correct 209 ms 20260 KB Output is correct
11 Correct 214 ms 20372 KB Output is correct
12 Correct 241 ms 24884 KB Output is correct
13 Correct 111 ms 20284 KB Output is correct
14 Correct 135 ms 19348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 22204 KB Output is correct
2 Correct 93 ms 21948 KB Output is correct
3 Correct 113 ms 24024 KB Output is correct
4 Correct 115 ms 24104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 23 ms 7076 KB Output is correct
8 Correct 318 ms 25728 KB Output is correct
9 Correct 299 ms 25668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 25668 KB Output is correct
2 Correct 183 ms 25004 KB Output is correct
3 Correct 181 ms 25156 KB Output is correct
4 Correct 182 ms 25168 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 19 ms 6604 KB Output is correct
7 Correct 250 ms 21144 KB Output is correct
8 Correct 303 ms 25668 KB Output is correct
9 Correct 127 ms 21384 KB Output is correct
10 Correct 159 ms 20604 KB Output is correct
11 Correct 124 ms 23380 KB Output is correct
12 Correct 125 ms 23524 KB Output is correct
13 Correct 181 ms 25200 KB Output is correct