oj.uz

Submission #521372

# Submission time Handle Problem Language Result Execution time Memory
521372 2022-02-02T01:56:41 Z amunduzbaev Synchronization (JOI13_synchronization) C++14
100 / 100
 253 ms 23404 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 1e5 + 5;
struct BIT{
	int tree[N];
	void add(int i, int v){ 
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int c = 0;
		for(;i>0;i-=(i&-i)) c += tree[i];
		return c;
	}
	
	int get(int l, int r){
		return get(r) - get(l - 1);
	}
}tree;

vector<int> edges[N];
int tin[N], tout[N], t, par[N][17];
int pre[N], is[N], cnt[N];

void dfs(int u, int p = -1){
	tin[u] = ++t, par[u][0] = p;
	for(int j=1;j<17;j++) par[u][j] = par[par[u][j-1]][j-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
	} tout[u] = t;
}

int get(int u){
	for(int j=16;~j;j--){
		if(tree.get(tin[par[u][j]]) == tree.get(tin[u])){
			u = par[u][j];
		}
	} return u;
}

void merge(int a, int b, int in){
	if(par[b][0] == a) swap(a, b);
	
	b = get(b);
	tree.add(tin[a], -1), tree.add(tout[a] + 1, 1);
	cnt[b] = cnt[b] + cnt[a] - pre[in];
}

void split(int a, int b, int in){
	if(par[b][0] == a) swap(a, b);
	
	b = get(b);
	tree.add(tin[a], 1), tree.add(tout[a] + 1, -1);
	pre[in] = cnt[a] = cnt[b];
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin>>n>>m>>k;
	vector<ar<int, 2>> e(n);
	for(int i=1;i<n;i++){
		cin>>e[i][0]>>e[i][1];
		edges[e[i][0]].push_back(e[i][1]);
		edges[e[i][1]].push_back(e[i][0]);
	}
	dfs(1, 1);
	for(int i=1;i<=n;i++){ cnt[i] = 1;
		tree.add(tin[i], 1), tree.add(tout[i] + 1, -1);
	}
	
	for(int i=0;i<m;i++){
		int j; cin>>j;
		if(is[j]){
			is[j] = 0;
			split(e[j][0], e[j][1], j);
		} else {
			is[j] = 1;
			merge(e[j][0], e[j][1], j);
		}
	}
	
	for(int i=1;i<n;i++) if(is[i]) split(e[i][0], e[i][1], i);
	while(k--){
		int u; cin>>u;
		cout<<cnt[u]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 16 ms 4192 KB Output is correct
8 Correct 15 ms 4172 KB Output is correct
9 Correct 16 ms 4140 KB Output is correct
10 Correct 206 ms 17928 KB Output is correct
11 Correct 220 ms 18244 KB Output is correct
12 Correct 216 ms 22528 KB Output is correct
13 Correct 105 ms 17784 KB Output is correct
14 Correct 181 ms 17392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 20100 KB Output is correct
2 Correct 111 ms 19900 KB Output is correct
3 Correct 138 ms 22036 KB Output is correct
4 Correct 129 ms 21904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 20 ms 4688 KB Output is correct
8 Correct 253 ms 23324 KB Output is correct
9 Correct 228 ms 23364 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 23404 KB Output is correct
2 Correct 145 ms 22928 KB Output is correct
3 Correct 142 ms 23140 KB Output is correct
4 Correct 149 ms 23076 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2676 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2664 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 17 ms 4220 KB Output is correct
7 Correct 232 ms 18868 KB Output is correct
8 Correct 251 ms 23268 KB Output is correct
9 Correct 117 ms 18920 KB Output is correct
10 Correct 191 ms 18688 KB Output is correct
11 Correct 126 ms 21228 KB Output is correct
12 Correct 133 ms 21272 KB Output is correct
13 Correct 145 ms 23148 KB Output is correct