oj.uz

Submission #255535

# Submission time Handle Problem Language Result Execution time Memory
255535 2020-08-01T07:58:09 Z oolimry Synchronization (JOI13_synchronization) C++14
100 / 100
 372 ms 26360 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;

int n, m, Q;
ii edges[100005];
bool open[100005];

vector<int> adj[100005];
int low[100005];
int high[100005];
int cnt = 0;

int p[100005][20];
void dfs(int u, int P){
	p[u][0] = P;
	for(int i = 1;i <= 19;i++) p[u][i] = p[p[u][i-1]][i-1];
	low[u] = cnt; high[u] = cnt; cnt++;
	
	for(int v : adj[u]){
		if(v == P) continue;
		dfs(v, u);
		high[u] = max(high[u], high[v]);
	}
}

int tree[200010];
void update(int l, int r, int v){
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1) tree[l++] += v;
		if(r&1) tree[--r] += v;
	}
}

int query(int i){
	int res = 0;
	for(i += n;i > 0;i >>= 1) res += tree[i];
	return res;
}

void disconnect(int u) { update(low[u], high[u]+1, 1); }
void connect(int u) { update(low[u], high[u]+1, -1); }
int findRoot(int u){
	for(int i = 19;i >= 0;i--){
		int nxt = p[u][i];
		if(nxt != 0 && query(low[nxt]) == query(low[u])) u = nxt;
	}
	return u;
}

int ans[100005]; ///how much stuff in there
int last[100005]; ///how much stuff previous time

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);	
	cin >> n >> m >> Q;
	
	for(int i = 1;i < n;i++){
		int u, v; cin >> u >> v;
		edges[i] = ii(u,v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	dfs(1,0);
	
	for(int i = 1;i <= n;i++){
		disconnect(i);
		ans[i] = 1;
	}
	
	while(m--){
		int e; cin >> e;
		int u = edges[e].first, v = edges[e].second;
		if(p[v][0] == u) swap(u,v); ///u will be child of v;
		
		if(!open[e]){ ///activate edge
			open[e] = true;
			ans[findRoot(v)] += ans[u] - last[u];
			connect(u);
		}
		else{ ///disactivate edge
			open[e] = false;
			ans[u] = last[u] = ans[findRoot(v)];
			disconnect(u);
		}
	}
	
	while(Q--){
		int u; cin >> u;
		cout << ans[findRoot(u)] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 13 ms 4352 KB Output is correct
8 Correct 19 ms 4352 KB Output is correct
9 Correct 20 ms 4352 KB Output is correct
10 Correct 228 ms 19448 KB Output is correct
11 Correct 216 ms 19320 KB Output is correct
12 Correct 307 ms 25592 KB Output is correct
13 Correct 105 ms 18876 KB Output is correct
14 Correct 156 ms 18396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 21752 KB Output is correct
2 Correct 122 ms 21628 KB Output is correct
3 Correct 156 ms 24696 KB Output is correct
4 Correct 141 ms 24568 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 23 ms 5112 KB Output is correct
8 Correct 371 ms 26232 KB Output is correct
9 Correct 368 ms 26344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 26360 KB Output is correct
2 Correct 211 ms 25712 KB Output is correct
3 Correct 227 ms 25720 KB Output is correct
4 Correct 224 ms 25696 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2944 KB Output is correct
6 Correct 18 ms 4480 KB Output is correct
7 Correct 275 ms 20216 KB Output is correct
8 Correct 372 ms 26236 KB Output is correct
9 Correct 123 ms 19940 KB Output is correct
10 Correct 197 ms 19576 KB Output is correct
11 Correct 164 ms 22996 KB Output is correct
12 Correct 169 ms 23056 KB Output is correct
13 Correct 230 ms 25720 KB Output is correct