Submission #841870

#	Time	Username	Problem	Language	Result	Execution time	Memory
841870		parsadox2	Synchronization (JOI13_synchronization)	C++14	100 / 100	206 ms	23756 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5 , L = 17;
int n , m , q , par[L][N] , tim , st[N] , fn[N] , fen[N] , ans[N] , las[N];
vector <int> adj[N];
vector <pair<int , int>> edges;
bool marked[N];

inline void Add(int x , int val)
{
	while(x <= n)
	{
		fen[x] += val;
		x += (x & -x);
	}
}

inline int Get(int x)
{
	int res = 0;
	while(x > 0)
	{
		res += fen[x];
		x -= (x & -x);
	}
	return res;
}

inline int root(int v)
{
	int now = Get(st[v]);
	for(int i = L - 1 ; i > -1 ; i--)
	{
		int tmp = Get(st[par[i][v]]);
		if(tmp == now && par[i][v] > 0)
		{
			v = par[i][v];
			now = tmp;
		}
	}
	return v;
}

void dfs(int v , int p)
{
	st[v] = tim++;
	for(auto u : adj[v])  if(u != p)
	{
		par[0][u] = v;
		dfs(u , v);
		Add(st[u] , +1);
		Add(fn[u] , -1);
	}
	fn[v] = tim;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int v , u;   cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
		edges.push_back({u , v});
	}
	tim = 1;
	dfs(1 , -1);
	for(int i = 1 ; i < L ; i++)  for(int j = 1 ; j <= n ; j++)
		par[i][j] = par[i - 1][par[i - 1][j]];
	for(int i = 1 ; i <= n ; i++)
		ans[i] = 1;
	while(m--)
	{
		int x;  cin >> x;  x--;
		int up = edges[x].first , dn = edges[x].second;
		if(par[0][up] == dn)
			swap(up , dn);
		if(marked[x])
		{
			ans[dn] = ans[root(dn)];
			las[dn] = ans[dn];
			Add(st[dn] , +1);
			Add(fn[dn] , -1);
			marked[x] = false;
		}
		else
		{
			ans[root(up)] += (ans[dn] - las[dn]);
			Add(st[dn] , -1);
			Add(fn[dn] , +1);
			marked[x] = true;
		}
	}
	while(q--)
	{
		int x;  cin >> x;
		cout << ans[root(x)] << '\n';
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40