oj.uz

Submission #398553

# Submission time Handle Problem Language Result Execution time Memory
398553 2021-05-04T13:54:46 Z nikatamliani Synchronization (JOI13_synchronization) C++14
100 / 100
 335 ms 27240 KB 
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int N = 2e5+10, LOG = 20;
int in[N], out[N], t[N], L[N][LOG], ans[N], last[N], is_active[N];
vector<int> g[N];
int n, m, q;
void dfs(int x, int p) {
	static int timer = 0;
	in[x] = ++timer;
	L[x][0] = p;
	for(int i = 1; i < LOG; ++i) {
		L[x][i] = L[L[x][i - 1]][i - 1];
	}
	for(int to : g[x]) {
		if(to != p) {
			dfs(to, x);
		}
	}
	out[x] = ++timer;
}
void upd(int x, int coeff) {
	for(; x <= 2*n; x += x & -x) {
		t[x] += coeff;
	}
}
int sum(int x) {
	int ans = 0;
	for(; x > 0; x -= x & -x) {
		ans += t[x];
	}
	return ans;
}
int parent(int x) {
	int me = sum(in[x]);
	for(int i = LOG - 1; i >= 0; --i) {
		if(L[x][i] && sum(in[L[x][i]]) == me) {
			x = L[x][i];
		}
	}
	return x;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	vector<array<int, 2>> e(n-1);
	for(auto &x : e) {
		cin >> x[0] >> x[1];
		g[x[0]].push_back(x[1]);
		g[x[1]].push_back(x[0]);
	}
	dfs(1, 0);
	for(int i = 0; i < n-1; ++i) {
		if(L[e[i][0]][0] == e[i][1]) {
			swap(e[i][0], e[i][1]);
		}
	}
	for(int i = 1; i <= n; ++i) {
		ans[i] = 1;
		upd(in[i], 1);
		upd(out[i], -1);
	}
	for(int i = 1; i <= m; ++i) {
		int id; cin >> id; --id;
		int par = e[id][0], child = e[id][1];
		if(is_active[id]) {
			last[child] = ans[child] = ans[parent(par)];
			upd(in[child], 1);
			upd(out[child], -1);
		} else { 
			ans[parent(par)] += ans[child] - last[child];
			upd(in[child], -1);
			upd(out[child], 1);
		}
		is_active[id] ^= 1;
	}
	for(int i = 1; i <= q; ++i) {
		int u; cin >> u;
		cout << ans[parent(u)] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 15 ms 6708 KB Output is correct
8 Correct 18 ms 6716 KB Output is correct
9 Correct 15 ms 6604 KB Output is correct
10 Correct 212 ms 21928 KB Output is correct
11 Correct 188 ms 21844 KB Output is correct
12 Correct 258 ms 26524 KB Output is correct
13 Correct 88 ms 21764 KB Output is correct
14 Correct 145 ms 20928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 21700 KB Output is correct
2 Correct 98 ms 23524 KB Output is correct
3 Correct 121 ms 25600 KB Output is correct
4 Correct 120 ms 25636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 22 ms 6984 KB Output is correct
8 Correct 330 ms 24408 KB Output is correct
9 Correct 303 ms 24356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 24448 KB Output is correct
2 Correct 172 ms 24364 KB Output is correct
3 Correct 171 ms 24440 KB Output is correct
4 Correct 174 ms 24392 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5032 KB Output is correct
5 Correct 5 ms 5304 KB Output is correct
6 Correct 19 ms 6732 KB Output is correct
7 Correct 267 ms 22748 KB Output is correct
8 Correct 335 ms 27240 KB Output is correct
9 Correct 109 ms 22972 KB Output is correct
10 Correct 170 ms 22340 KB Output is correct
11 Correct 134 ms 24944 KB Output is correct
12 Correct 133 ms 24964 KB Output is correct
13 Correct 179 ms 26748 KB Output is correct