oj.uz

답안 #398551

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398551 2021-05-04T13:53:04 Z nikatamliani 동기화 (JOI13_synchronization) C++14
30 / 100
 330 ms 26892 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 <= 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Incorrect 3 ms 5068 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 23408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5000 KB Output is correct
6 Correct 5 ms 5268 KB Output is correct
7 Correct 21 ms 7172 KB Output is correct
8 Correct 330 ms 26848 KB Output is correct
9 Correct 330 ms 26884 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 26892 KB Output is correct
2 Correct 181 ms 26248 KB Output is correct
3 Correct 196 ms 26308 KB Output is correct
4 Correct 175 ms 26408 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Incorrect 5 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -