oj.uz

Submission #841870

# Submission time Handle Problem Language Result Execution time Memory
841870 2023-09-02T07:53:53 Z parsadox2 Synchronization (JOI13_synchronization) C++14
100 / 100
 206 ms 23756 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 9 ms 11100 KB Output is correct
8 Correct 9 ms 11096 KB Output is correct
9 Correct 9 ms 11100 KB Output is correct
10 Correct 106 ms 15312 KB Output is correct
11 Correct 94 ms 15300 KB Output is correct
12 Correct 134 ms 23248 KB Output is correct
13 Correct 74 ms 15824 KB Output is correct
14 Correct 63 ms 15308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 19368 KB Output is correct
2 Correct 55 ms 19360 KB Output is correct
3 Correct 56 ms 23232 KB Output is correct
4 Correct 56 ms 23196 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 15 ms 11868 KB Output is correct
8 Correct 206 ms 23356 KB Output is correct
9 Correct 180 ms 23344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 23240 KB Output is correct
2 Correct 96 ms 23656 KB Output is correct
3 Correct 93 ms 23632 KB Output is correct
4 Correct 93 ms 23704 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 3 ms 10804 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 11 ms 11328 KB Output is correct
7 Correct 144 ms 15788 KB Output is correct
8 Correct 167 ms 23244 KB Output is correct
9 Correct 87 ms 16324 KB Output is correct
10 Correct 84 ms 16120 KB Output is correct
11 Correct 79 ms 20300 KB Output is correct
12 Correct 78 ms 20040 KB Output is correct
13 Correct 93 ms 23756 KB Output is correct