oj.uz

Submission #841868

# Submission time Handle Problem Language Result Execution time Memory
841868 2023-09-02T07:52:12 Z parsadox2 Synchronization (JOI13_synchronization) C++14
100 / 100
 303 ms 26700 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10 , M = 2e5 + 10 , L = 18;
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];

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

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

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 2 ms 10588 KB Output is correct
2 Correct 2 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 2 ms 10588 KB Output is correct
6 Correct 2 ms 10808 KB Output is correct
7 Correct 12 ms 11356 KB Output is correct
8 Correct 10 ms 11356 KB Output is correct
9 Correct 10 ms 11356 KB Output is correct
10 Correct 114 ms 18120 KB Output is correct
11 Correct 105 ms 18120 KB Output is correct
12 Correct 184 ms 26056 KB Output is correct
13 Correct 59 ms 18000 KB Output is correct
14 Correct 71 ms 17456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 21704 KB Output is correct
2 Correct 58 ms 21704 KB Output is correct
3 Correct 67 ms 25256 KB Output is correct
4 Correct 68 ms 25244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10764 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 10800 KB Output is correct
7 Correct 15 ms 12336 KB Output is correct
8 Correct 213 ms 26576 KB Output is correct
9 Correct 236 ms 26700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 26572 KB Output is correct
2 Correct 110 ms 26420 KB Output is correct
3 Correct 112 ms 26392 KB Output is correct
4 Correct 108 ms 26528 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 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 3 ms 10804 KB Output is correct
6 Correct 12 ms 11376 KB Output is correct
7 Correct 135 ms 19056 KB Output is correct
8 Correct 303 ms 26584 KB Output is correct
9 Correct 73 ms 19088 KB Output is correct
10 Correct 89 ms 18888 KB Output is correct
11 Correct 80 ms 22984 KB Output is correct
12 Correct 81 ms 23084 KB Output is correct
13 Correct 108 ms 26548 KB Output is correct