oj.uz

Submission #379262

# Submission time Handle Problem Language Result Execution time Memory
379262 2021-03-17T18:02:51 Z wind_reaper Synchronization (JOI13_synchronization) C++17
100 / 100
 592 ms 23148 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];

int inc(int x){
	return x & (-x);
}

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

int query(int idx){
	int sum = 0;
	for(; idx; idx -= inc(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 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2668 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 3820 KB Output is correct
8 Correct 13 ms 3820 KB Output is correct
9 Correct 13 ms 3820 KB Output is correct
10 Correct 223 ms 13548 KB Output is correct
11 Correct 247 ms 13548 KB Output is correct
12 Correct 524 ms 22304 KB Output is correct
13 Correct 77 ms 11748 KB Output is correct
14 Correct 165 ms 12876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 17996 KB Output is correct
2 Correct 84 ms 17772 KB Output is correct
3 Correct 106 ms 21356 KB Output is correct
4 Correct 111 ms 21356 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 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 24 ms 4716 KB Output is correct
8 Correct 511 ms 23148 KB Output is correct
9 Correct 534 ms 23148 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 23148 KB Output is correct
2 Correct 168 ms 22508 KB Output is correct
3 Correct 166 ms 22508 KB Output is correct
4 Correct 170 ms 22636 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 3 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 3948 KB Output is correct
7 Correct 310 ms 14812 KB Output is correct
8 Correct 526 ms 23020 KB Output is correct
9 Correct 102 ms 13028 KB Output is correct
10 Correct 191 ms 13804 KB Output is correct
11 Correct 124 ms 19180 KB Output is correct
12 Correct 140 ms 19180 KB Output is correct
13 Correct 174 ms 22508 KB Output is correct