Submission #417447

#	Time	Username	Problem	Language	Result	Execution time	Memory
417447		MohamedAhmed04	Synchronization (JOI13_synchronization)	C++17	100 / 100	318 ms	25728 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40