oj.uz

Submission #839118

# Submission time Handle Problem Language Result Execution time Memory
839118 2023-08-28T17:31:28 Z serifefedartar Synchronization (JOI13_synchronization) C++17
100 / 100
 478 ms 28824 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005

vector<vector<int>> graph;
vector<pair<int,int>> edges;
int fen[2*MAXN], tin[MAXN], tout[MAXN];
int up[LOGN][MAXN], val[MAXN], sync_up[MAXN];
int par[MAXN], active[MAXN], depth[MAXN];
void update(int k, int val) {
	while (k < 2*MAXN) {
		fen[k] += val;
		k += k&-k;
	}
}

int query(int k) {
	int res = 0;
	while (k) {
		res += fen[k];
		k -= k&-k;
	}
	return res;
}
	
int T = 0;
void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u, node); 
	}
	tout[node] = ++T;
}

int upmost(int node) {
	for (int i = LOGN-1; i >= 0; i--) {
		if (query(tin[node]) == query(tin[up[i][node]]))
			node = up[i][node];
	}
	return node;
}

int main() {
	fast
	int N, M, Q, A, B;
	cin >> N >> M >> Q;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i <= N; i++)
		val[i] = 1;
	for (int i = 1; i < N; i++) {
		cin >> A >> B;
		graph[A].push_back(B);
		graph[B].push_back(A);
		edges.push_back({A, B});
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1; 
	dfs(1, 1);

	for (int i = 1; i <= N; i++) {
		update(tin[i], 1);
		update(tout[i]+1, -1);
	}

	for (int i = 0; i < M; i++) {
		int x, up, down;
		cin >> x;
		if (depth[edges[x-1].f] > depth[edges[x-1].s])
			down = edges[x-1].f, up = edges[x-1].s;
		else
			down = edges[x-1].s, up = edges[x-1].f;

		if (active[x]) {
			par[down] = down;
			val[down] = val[upmost(down)]; 
			sync_up[down] = val[down];
			update(tin[down], 1);
			update(tout[down]+1, -1);
			active[x] = false;
		} else {
			par[down] = upmost(up);
			val[par[down]] = val[par[down]] + val[down] - sync_up[down];
			update(tin[down], -1);
			update(tout[down]+1, 1);
			active[x] = true;
		}
	}

	while (Q--) {
		int x;
		cin >> x;
		cout << val[upmost(x)] << "\n"; 
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 15 ms 2396 KB Output is correct
8 Correct 15 ms 2492 KB Output is correct
9 Correct 15 ms 2388 KB Output is correct
10 Correct 321 ms 20448 KB Output is correct
11 Correct 324 ms 20336 KB Output is correct
12 Correct 416 ms 28044 KB Output is correct
13 Correct 82 ms 20240 KB Output is correct
14 Correct 185 ms 19288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 21700 KB Output is correct
2 Correct 78 ms 21528 KB Output is correct
3 Correct 95 ms 25540 KB Output is correct
4 Correct 89 ms 25316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 19 ms 3028 KB Output is correct
8 Correct 375 ms 25888 KB Output is correct
9 Correct 388 ms 25892 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 25920 KB Output is correct
2 Correct 148 ms 25920 KB Output is correct
3 Correct 136 ms 26004 KB Output is correct
4 Correct 138 ms 25916 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 18 ms 2516 KB Output is correct
7 Correct 363 ms 21096 KB Output is correct
8 Correct 478 ms 28824 KB Output is correct
9 Correct 130 ms 21324 KB Output is correct
10 Correct 189 ms 20564 KB Output is correct
11 Correct 109 ms 25024 KB Output is correct
12 Correct 107 ms 24872 KB Output is correct
13 Correct 137 ms 28248 KB Output is correct