Submission #751027

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751027	2023-05-30T20:12:03 Z	jmyszka2007	Synchronization (JOI13_synchronization)	C++17	100 / 100	737 ms	30436 KB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
constexpr int LIM = 2e5;
constexpr int base = (1 << 18);
pair<int, int>kr[LIM + 10];
vector<int>g[LIM + 10];
int kt[LIM + 10];
int val[LIM + 10];
int pop[LIM + 10];
int nxt[LIM + 10][19];
int siz[LIM + 10];
int pre[LIM + 10];
int dep[LIM + 10];
int tri[2 * base];
int aktpre = 1;
void dfs(int v, int o) {
	dep[v] = dep[o] + 1;
	pre[v] = aktpre++;
	nxt[v][0] = o;
	for(int i = 1; i <= 18; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
	}
	siz[v] = 1;
	for(auto x : g[v]) {
		if(x != o) {
			dfs(x, v);
			siz[v] += siz[x];
		}
	}
}
void upd(int l, int r, int x) {
	l += base;
	r += base;
	while(l <= r) {
		if(l & 1) {
			tri[l] += x;
		}
		if(!(r & 1)) {
			tri[r] += x;
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}
int que(int v) {
	v += base;
	int ans = 0;
	while(v > 0) {
		ans += tri[v];
		v /= 2;
	}
	return ans;
}
int find(int v) {
	for(int i = 18; i >= 0; i--) {
		if(que(pre[v]) - que(pre[nxt[v][i]]) == dep[v] - dep[nxt[v][i]]) {
			v = nxt[v][i];
		}
	}
	return v;
}
void uni(int a, int b) {
	if(pre[a] > pre[b]) {
		swap(a, b);
	}
	upd(pre[b], pre[b] + siz[b] - 1, 1); 
}
void disuni(int a, int b) {
	if(pre[a] > pre[b]) {
		swap(a, b);
	}
	upd(pre[b], pre[b] + siz[b] - 1, -1); 
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++) {
		val[i] = 1;
	}
	for(int i = 1; i < n; i++) {
		cin >> kr[i].st >> kr[i].nd;
		g[kr[i].st].push_back(kr[i].nd);
		g[kr[i].nd].push_back(kr[i].st);
	}
	dfs(1, 1);
	for(int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		kt[x]++;
		if(kt[x] & 1) {
			int tmp = val[find(kr[x].st)] + val[find(kr[x].nd)] - pop[x];
			uni(kr[x].st, kr[x].nd);
			val[find(kr[x].st)] = tmp;
		}
		else {
			pop[x] = val[find(kr[x].st)];
			disuni(kr[x].st, kr[x].nd);
			val[find(kr[x].st)] = pop[x];
			val[find(kr[x].nd)] = pop[x];
		}
	}
	while(q--) {
		int x;
		cin >> x;
		cout << val[find(x)] << '\n';
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	3 ms	5032 KB	Output is correct
4	Correct	3 ms	5076 KB	Output is correct
5	Correct	4 ms	5076 KB	Output is correct
6	Correct	8 ms	5264 KB	Output is correct
7	Correct	49 ms	6724 KB	Output is correct
8	Correct	51 ms	6732 KB	Output is correct
9	Correct	50 ms	6740 KB	Output is correct
10	Correct	608 ms	22080 KB	Output is correct
11	Correct	587 ms	21952 KB	Output is correct
12	Correct	588 ms	29664 KB	Output is correct
13	Correct	484 ms	21448 KB	Output is correct
14	Correct	320 ms	20900 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	495 ms	23908 KB	Output is correct
2	Correct	496 ms	24900 KB	Output is correct
3	Correct	244 ms	28712 KB	Output is correct
4	Correct	247 ms	28668 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	3 ms	5032 KB	Output is correct
4	Correct	3 ms	5032 KB	Output is correct
5	Correct	3 ms	5028 KB	Output is correct
6	Correct	8 ms	5304 KB	Output is correct
7	Correct	54 ms	7552 KB	Output is correct
8	Correct	625 ms	30432 KB	Output is correct
9	Correct	668 ms	30436 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	663 ms	29016 KB	Output is correct
2	Correct	327 ms	29776 KB	Output is correct
3	Correct	327 ms	29992 KB	Output is correct
4	Correct	347 ms	29912 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	3 ms	5076 KB	Output is correct
4	Correct	4 ms	5076 KB	Output is correct
5	Correct	9 ms	5204 KB	Output is correct
6	Correct	60 ms	6784 KB	Output is correct
7	Correct	737 ms	22712 KB	Output is correct
8	Correct	669 ms	30432 KB	Output is correct
9	Correct	560 ms	22572 KB	Output is correct
10	Correct	442 ms	22272 KB	Output is correct
11	Correct	597 ms	26440 KB	Output is correct
12	Correct	642 ms	26408 KB	Output is correct
13	Correct	327 ms	29896 KB	Output is correct