oj.uz

답안 #751027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751027 2023-05-30T20:12:03 Z jmyszka2007 동기화 (JOI13_synchronization) C++17
100 / 100
 737 ms 30436 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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