oj.uz

Submission #379264

# Submission time Handle Problem Language Result Execution time Memory
379264 2021-03-17T18:10:55 Z wind_reaper Synchronization (JOI13_synchronization) C++17
100 / 100
 551 ms 20588 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 100001;
const int lg = 20;

int n, m, q;
bool active[MXN];

vector<int> adj[MXN];
int a[MXN], c[MXN];

int up[lg][MXN];
int tin[MXN], tout[MXN];
int timer = 1;

void dfs(int node = 1, int par = 0){
	tin[node] = timer++;
	a[node] = 1;

	up[0][node] = par;
	for(int i = 1; i < lg && up[i-1][node]; i++)
		up[i][node] = up[i-1][up[i-1][node]];

	for(int v : adj[node]){
		if(v == par)
			continue;
		dfs(v, node);
	}

	tout[node] = timer;
}

int tree[MXN];

void upd(int idx, int val){
	for(; idx <= n; idx += (idx&(-idx)))
		tree[idx] += val;
}

int query(int idx){
	int sum = 0;
	for(; idx; idx -= (idx&(-idx)))
		sum += tree[idx];
	return sum;
}

int findAncestor(int node){
	int lca = node;
	int ct = query(tin[node]);
	for(int i = lg-1; i >= 0; --i)
		if(up[i][lca] && query(tin[up[i][lca]]) == ct)
			lca = up[i][lca];

	return lca;
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	cin >> n >> m >> q;

	vector<array<int, 2>> edges(n-1);
	for(auto& [u, v] : edges){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs();

	for(int i = 1; i <= n; i++){
		upd(tin[i], 1);
		upd(tout[i], -1);
	}

	for(int i = 0; i < m; i++){
		int idx;
		cin >> idx;
		--idx;
		int u = edges[idx][0], v = edges[idx][1];

		if(up[0][u] == v)
			swap(u, v);

		if(active[idx]){
			a[v] = c[v] = a[findAncestor(u)];
			upd(tin[v], 1);
			upd(tout[v], -1);
		}
		else{
			a[findAncestor(u)] += (a[v] - c[v]);
			upd(tin[v], -1);
			upd(tout[v], 1);
		}

		active[idx] = !active[idx];
	}

	for(int i = 0; i < q; i++){
		int node;
		cin >> node;
		cout << a[findAncestor(node)] << '\n';
	}
	return 0; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 13 ms 3840 KB Output is correct
8 Correct 13 ms 3820 KB Output is correct
9 Correct 13 ms 3820 KB Output is correct
10 Correct 221 ms 11500 KB Output is correct
11 Correct 271 ms 11520 KB Output is correct
12 Correct 424 ms 20204 KB Output is correct
13 Correct 81 ms 10084 KB Output is correct
14 Correct 169 ms 11372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 16256 KB Output is correct
2 Correct 84 ms 16108 KB Output is correct
3 Correct 106 ms 19820 KB Output is correct
4 Correct 106 ms 19820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 22 ms 4588 KB Output is correct
8 Correct 509 ms 20460 KB Output is correct
9 Correct 523 ms 20480 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 20588 KB Output is correct
2 Correct 166 ms 20504 KB Output is correct
3 Correct 163 ms 20460 KB Output is correct
4 Correct 167 ms 20460 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 17 ms 3820 KB Output is correct
7 Correct 292 ms 12012 KB Output is correct
8 Correct 538 ms 20332 KB Output is correct
9 Correct 104 ms 10704 KB Output is correct
10 Correct 183 ms 11756 KB Output is correct
11 Correct 144 ms 16876 KB Output is correct
12 Correct 130 ms 16964 KB Output is correct
13 Correct 165 ms 20460 KB Output is correct