oj.uz

답안 #309392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309392 2020-10-03T12:48:12 Z Hehehe 동기화 (JOI13_synchronization) C++14
0 / 100
 381 ms 17892 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m, q;
int cnt;
int res[N], lst[N];
int h[N], st[N], ed[N], pos[N];
int from[N], to[N];
int it[4 * N];
bool type[N];
vector<int> G[N];

void dfs(int u, int p) {
	st[u] = ++cnt, pos[cnt] = u;
	for (auto v : G[u]) {
		if (v == p) continue;
		h[v] = h[u] + 1, dfs(v, u);
	}
	ed[u] = cnt;
}

void build(int i, int l, int r) {
	if (l == r) {
		it[i] = ed[pos[l]]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void upd(int i, int l, int r, int p, int x) {
	if (l == r) {
		it[i] = x; return;
	}
	int mid = (l + r) >> 1;
	if (mid >= p) upd(i << 1, l, mid, p, x);
	else upd(i << 1 | 1, mid + 1, r, p, x);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}

int find(int i, int l, int r, int u, int v) {
	if (l > u || it[i] < v) return -1;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = find(i << 1 | 1, mid + 1, r, u, v);
	if (res != -1) return res;
	return find(i << 1, l, mid, u, v);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		cin >> from[i] >> to[i];
		G[from[i]].push_back(to[i]);
		G[to[i]].push_back(from[i]);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; ++i) res[i] = 1;
	build(1, 1, n);
	for (int i = 1; i < n; ++i) {
		if (h[from[i]] > h[to[i]]) swap(from[i], to[i]);
	}
	for (int i = 1; i <= m; ++i) {
		int x; cin >> x; //cout << from[x] << ' ' << to[x] << '\n';
		if (!type[x]) {
			res[pos[st[from[x]]]] += res[to[x]] - lst[x]; //cout << "E    " << st[from[x]] << ' ' << find(1, 1, n, st[from[x]], ed[from[x]]) << '\n';
			upd(1, 1, n, st[to[x]], 0);
		}
		else {
			res[to[x]] = lst[x] = res[pos[find(1, 1, n, st[from[x]], ed[from[x]])]];
			upd(1, 1, n, st[to[x]], ed[to[x]]);
		}
		type[x] ^= 1;
	}
	for (int i = 1; i <= q; ++i) {
		int x; cin >> x; cout << res[pos[find(1, 1, n, st[x], ed[x])]] << '\n';
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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