oj.uz

Submission #263854

# Submission time Handle Problem Language Result Execution time Memory
263854 2020-08-14T02:41:30 Z atoiz Synchronization (JOI13_synchronization) C++14
100 / 100
 161 ms 16888 KB 
// https://oj.uz/submission/151967

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100007;

int par[MAXN], ch[MAXN][2];
bool isroot(int u) { return (u != ch[par[u]][0] && u != ch[par[u]][1]); }
bool dir(int u) { return (u == ch[par[u]][1]); }
void rotate(int u) 
{
	int p = par[u], g = par[p], d = dir(u);
	if (!isroot(p)) { ch[g][dir(p)] = u; } par[u] = g;
	par[ch[p][d] = ch[u][!d]] = p, par[ch[u][!d] = p] = u;
}
void splay(int u) { for (; !isroot(u); rotate(u)) if (!isroot(par[u])) rotate(dir(u) == dir(par[u]) ? par[u] : u); }
void access(int u) { for (int v = 0; u; v = u, u = par[v]) splay(u), ch[u][1] = v; }
int get(int u)
{
	access(u), splay(u);
	while (ch[u][0]) u = ch[u][0];
	splay(u);
	return u;
}

int N, M, Q, last[MAXN], ans[MAXN], U[MAXN], V[MAXN], prv[MAXN];
bool state[MAXN];
vector<int> G[MAXN];

void dfs(int u, int p) { for (int v : G[u]) if (v != p) dfs(v, prv[v] = u); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i < N; ++i) {
		cin >> U[i] >> V[i];
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	dfs(1, 0);
	for (int u = 1; u <= N; ++u) ans[u] = 1;
	while (M--) {
		int e;
		cin >> e;
		int u = U[e], v = V[e];
		if (prv[v] != u) swap(u, v);
		int r = get(u);
		if (state[e]) {
			last[v] = ans[v] = ans[r];
			access(v), splay(v), par[u] = ch[v][0] = 0;
		} else {
			ans[r] += (ans[v] - last[v]);
			access(v), splay(v), par[v] = u;
		}
		state[e] = !state[e];
	}
	while (Q--) {
		int u;
		cin >> u;
		cout << ans[get(u)] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 10 ms 3712 KB Output is correct
8 Correct 10 ms 3584 KB Output is correct
9 Correct 9 ms 3584 KB Output is correct
10 Correct 102 ms 11512 KB Output is correct
11 Correct 96 ms 11512 KB Output is correct
12 Correct 80 ms 15992 KB Output is correct
13 Correct 63 ms 11372 KB Output is correct
14 Correct 78 ms 10492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13368 KB Output is correct
2 Correct 63 ms 13176 KB Output is correct
3 Correct 56 ms 15096 KB Output is correct
4 Correct 59 ms 15096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 12 ms 4128 KB Output is correct
8 Correct 105 ms 16888 KB Output is correct
9 Correct 111 ms 16888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 16888 KB Output is correct
2 Correct 86 ms 16244 KB Output is correct
3 Correct 89 ms 16312 KB Output is correct
4 Correct 86 ms 16376 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 12 ms 3712 KB Output is correct
7 Correct 141 ms 12324 KB Output is correct
8 Correct 116 ms 16888 KB Output is correct
9 Correct 96 ms 12528 KB Output is correct
10 Correct 161 ms 11896 KB Output is correct
11 Correct 91 ms 14584 KB Output is correct
12 Correct 91 ms 14584 KB Output is correct
13 Correct 87 ms 16376 KB Output is correct