oj.uz

Submission #529014

# Submission time Handle Problem Language Result Execution time Memory
529014 2022-02-21T22:32:09 Z blue Synchronization (JOI13_synchronization) C++17
100 / 100
 247 ms 26240 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int mx = 100'000;
const int lg = 18;

using pii = pair<int, int>;
using vi = vector<int>;
using vpii = vector<pii>;

int N, M, Q;

vpii edge[1 + mx];

vi edge_node(1 + mx);
vi node_edge(1 + mx);
vi par(1 + mx, 0);

vi subtree(1 + mx, 1);
vi ord_ind(1 + mx, 0);
int ord_ct = 0;

int anc[1 + mx][1 + lg];



void dfs(int u)
{
	ord_ind[u] = ++ord_ct;

	for(auto ed : edge[u])
	{
		int v = ed.first;
		int e = ed.second;

		if(v == par[u]) continue;

		par[v] = u;
		edge_node[e] = v;
		node_edge[v] = e;

		dfs(v);

		subtree[u] += subtree[v];
	}
}

vi BIT(1 + mx, 0);



vi label_data(1 + mx, 1);
vi par_data(1 + mx, 0);
vi par_enabled(1 + mx, 0);


void bitadd(int i, int v)
{
	for(int j = i; j <= N; j += j&-j)
		BIT[j] += v;
}


int getblocked(int u)
{
	int p = ord_ind[u];
	int res = 0;
	for(int i = p; i >= 1; i -= i&-i)
		res += BIT[i];
	return res;
}

int getlabel(int u)
{
	int ub = getblocked(u);

	for(int e = lg; e >= 0; e--)
	{
		int v = anc[u][e];
		if(v == 0) continue;
		if(getblocked(v) != ub) continue;
		u = v;
	}

	return u;
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> Q;

	for(int e = 1; e <= N-1; e++)
	{
		int x, y;
		cin >> x >> y;
		edge[x].push_back({y, e});
		edge[y].push_back({x, e});
	}

	dfs(1);


	anc[0][0] = 0;
	for(int i = 1; i <= N; i++) anc[i][0] = par[i];
	for(int e = 1; e <= lg; e++)
		for(int i = 0; i <= N; i++)
			anc[i][e] = anc[ anc[i][e-1] ][e-1];

	for(int u = 1; u <= N; u++)
	{
		bitadd(ord_ind[u], +1);
		bitadd(ord_ind[u] + subtree[u], -1);
	}


	for(int o = 1; o <= M; o++)
	{
		int e;
		cin >> e;

		int u = edge_node[e];

		if(par_enabled[u])
		{
			int glu = getlabel(u);

			par_data[u] = label_data[glu];
			par_enabled[u] = 0;

			label_data[u] = label_data[glu];

			bitadd(ord_ind[u], +1);
			bitadd(ord_ind[u] + subtree[u], -1);
		}
		else
		{
			int glpu = getlabel(par[u]);

			par_enabled[u] = 1;

			label_data[glpu] = label_data[glpu] + label_data[u] - par_data[u];

			bitadd(ord_ind[u], -1);
			bitadd(ord_ind[u] + subtree[u], +1);
		}
	}



	for(int q = 1; q <= Q; q++)
	{
		int C;
		cin >> C;

		cout << label_data[getlabel(C)] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Correct 3 ms 6092 KB Output is correct
5 Correct 3 ms 6220 KB Output is correct
6 Correct 4 ms 6348 KB Output is correct
7 Correct 13 ms 7500 KB Output is correct
8 Correct 13 ms 7512 KB Output is correct
9 Correct 12 ms 7504 KB Output is correct
10 Correct 197 ms 19656 KB Output is correct
11 Correct 140 ms 19664 KB Output is correct
12 Correct 189 ms 25292 KB Output is correct
13 Correct 82 ms 19396 KB Output is correct
14 Correct 94 ms 19012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 22196 KB Output is correct
2 Correct 83 ms 22020 KB Output is correct
3 Correct 92 ms 24772 KB Output is correct
4 Correct 91 ms 24660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6092 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 3 ms 6220 KB Output is correct
4 Correct 3 ms 6212 KB Output is correct
5 Correct 3 ms 6220 KB Output is correct
6 Correct 4 ms 6360 KB Output is correct
7 Correct 18 ms 8152 KB Output is correct
8 Correct 247 ms 26240 KB Output is correct
9 Correct 246 ms 26076 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 26080 KB Output is correct
2 Correct 132 ms 25696 KB Output is correct
3 Correct 135 ms 25860 KB Output is correct
4 Correct 134 ms 25820 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6220 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 3 ms 6092 KB Output is correct
4 Correct 3 ms 6228 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 15 ms 7508 KB Output is correct
7 Correct 168 ms 20468 KB Output is correct
8 Correct 234 ms 26172 KB Output is correct
9 Correct 102 ms 20568 KB Output is correct
10 Correct 121 ms 20280 KB Output is correct
11 Correct 107 ms 23488 KB Output is correct
12 Correct 119 ms 23492 KB Output is correct
13 Correct 137 ms 25924 KB Output is correct