oj.uz

Submission #88106

# Submission time Handle Problem Language Result Execution time Memory
88106 2018-12-03T20:04:45 Z KCSC Synchronization (JOI13_synchronization) C++14
100 / 100
 687 ms 68468 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;

int sgt[DIM * 8], fst[DIM], lst[DIM], oans[DIM], nans[DIM], lev[DIM];
vector<int> edg[DIM]; pair<int, int> lis[DIM]; bitset<DIM> oki;

void dfs(int x, int f) {
	static int cnt = 0;
	fst[x] = ++cnt; lev[x] = lev[f] + 1;
	for (int y : edg[x]) { 
		if (y != f) { 
			dfs(y, x); } }
	lst[x] = ++cnt; }

void update(int nd, int le, int ri, int ps, int vl) {
	if (le == ri) {
		sgt[nd] += vl; }
	else {
		int md = (le + ri) / 2;
		if (ps <= md) {
			update(nd << 1, le, md, ps, vl); }
		else {
			update(nd << 1 | 1, md + 1, ri, ps, vl); }
		if (lst[sgt[nd << 1]] > lst[sgt[nd << 1 | 1]]) {
			sgt[nd] = sgt[nd << 1]; }
		else {
			sgt[nd] = sgt[nd << 1 | 1]; } } }

int find(int nd, int le, int ri, int ps, int vl) {
	if (ps < le or (ri <= ps and lst[sgt[nd]] < lst[vl])) {
		return 0; }
	if (le == ri) {
		return sgt[nd]; }
	int md = (le + ri) / 2,
		rt = find(nd << 1 | 1, md + 1, ri, ps, vl);
	if (rt) {
		return rt; }
	else {
		return find(nd << 1, le, md, ps, vl); } }
	
int main(void) {
#ifdef HOME
	freopen("synchronization.in", "r", stdin);
	freopen("synchronization.out", "w", stdout);
#endif
	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		int x, y; cin >> x >> y;
		edg[x].push_back(y); edg[y].push_back(x);
		lis[i] = make_pair(x, y); }
	dfs(1, 0);
	for (int i = 1; i <= n; ++i) {
		update(1, 1, n << 1, fst[i], i); nans[i] = 1; }
	while (m--) {
		int id; cin >> id;
		int x = lis[id].first, y = lis[id].second;
		if (lev[x] > lev[y]) {
			swap(x, y); }
		int z = find(1, 1, n << 1, fst[x], x);
		if (!oki[id]) {
			nans[z] += nans[y] - oans[y];
			update(1, 1, n << 1, fst[y], -y); }
		else {
			nans[y] = nans[z];
			update(1, 1, n << 1, fst[y], y); }
		oans[y] = nans[y]; oki[id] = oki[id] ^ 1; }
	while (q--) {
		int x; cin >> x;
		cout << nans[find(1, 1, n << 1, fst[x], x)] << "\n"; }
	return 0; }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2972 KB Output is correct
3 Correct 5 ms 3032 KB Output is correct
4 Correct 4 ms 3032 KB Output is correct
5 Correct 5 ms 3032 KB Output is correct
6 Correct 7 ms 3132 KB Output is correct
7 Correct 33 ms 4088 KB Output is correct
8 Correct 32 ms 4432 KB Output is correct
9 Correct 32 ms 4532 KB Output is correct
10 Correct 442 ms 14188 KB Output is correct
11 Correct 441 ms 16416 KB Output is correct
12 Correct 334 ms 22368 KB Output is correct
13 Correct 298 ms 22368 KB Output is correct
14 Correct 303 ms 22368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 26448 KB Output is correct
2 Correct 218 ms 28508 KB Output is correct
3 Correct 181 ms 31944 KB Output is correct
4 Correct 192 ms 33504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33504 KB Output is correct
2 Correct 5 ms 33504 KB Output is correct
3 Correct 5 ms 33504 KB Output is correct
4 Correct 5 ms 33504 KB Output is correct
5 Correct 5 ms 33504 KB Output is correct
6 Correct 9 ms 33504 KB Output is correct
7 Correct 50 ms 33504 KB Output is correct
8 Correct 545 ms 37172 KB Output is correct
9 Correct 545 ms 39988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 42836 KB Output is correct
2 Correct 412 ms 45312 KB Output is correct
3 Correct 407 ms 47748 KB Output is correct
4 Correct 406 ms 49976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 49976 KB Output is correct
2 Correct 4 ms 49976 KB Output is correct
3 Correct 4 ms 49976 KB Output is correct
4 Correct 5 ms 49976 KB Output is correct
5 Correct 9 ms 49976 KB Output is correct
6 Correct 58 ms 49976 KB Output is correct
7 Correct 687 ms 49976 KB Output is correct
8 Correct 506 ms 55772 KB Output is correct
9 Correct 520 ms 55772 KB Output is correct
10 Correct 515 ms 57352 KB Output is correct
11 Correct 456 ms 61960 KB Output is correct
12 Correct 460 ms 64520 KB Output is correct
13 Correct 416 ms 68468 KB Output is correct