oj.uz

Submission #869123

# Submission time Handle Problem Language Result Execution time Memory
869123 2023-11-03T09:08:00 Z alex_2008 Synchronization (JOI13_synchronization) C++14
100 / 100
 424 ms 27332 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <set>
#include <tuple>
#include <vector>
#include <iomanip>
#include <queue>
#define yy second
#define xx first
typedef long double ld;
using namespace std;
const int N = 2e5 + 10;
vector <vector<int>> G;
int n;
int inf[N], last[N], tin[N], tout[N], dp[N][20], fenwick[N];
bool ch[N];
int timer = 0;
void dfs(int v, int p) {
	dp[v][0] = p;
	for (int i = 1; i < 20; i++) {
		dp[v][i] = dp[dp[v][i - 1]][i - 1];
	}
	tin[v] = ++timer;
	for (auto it : G[v]) {
		if (it == p) continue;
		dfs(it, v);
	}
	tout[v] = ++timer;
}
void update(int pos, int val) {
	for (int i = pos; i <= 2 * n; i += (i & (-i))) {
		fenwick[i] += val;
	}
}
int sum(int pos) {
	int sm = 0;
	while (pos > 0) {
		sm += fenwick[pos];
		pos -= (pos & (-pos));
	}
	return sm;
}
int par(int v) {
	for (int i = 19; i >= 0; i--) {
		if (sum(tin[dp[v][i]]) == sum(tin[v])) {
			v = dp[v][i];
		}
	}
	return v;
}
int main()
{
	int m, q;
	cin >> n >> m >> q;
	G.resize(n + 1);
	vector <pair<int, int>> Edges = { { 0, 0 } };
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
		Edges.push_back({ a, b });
	}
	for (int i = 1; i <= n; i++) {
		inf[i] = 1;
		last[i] = 0;
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		update(tin[i], -1);
		update(tout[i], 1);
	}
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		int v = Edges[x].first, u = Edges[x].second;
		if (dp[u][0] == v) swap(v, u);
		if (ch[v]) {
			inf[v] = last[v] = inf[par(u)];
			update(tin[v], -1);
			update(tout[v], 1);
		}
		else {
			inf[par(u)] += (inf[v] - last[v]);
			update(tin[v], 1);
			update(tout[v], -1);
		}
		ch[v] = 1 - ch[v];
	}
	for (int i = 1; i <= q; i++) {
		int x;
		cin >> x;
		cout << inf[par(x)] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 18 ms 5232 KB Output is correct
8 Correct 17 ms 5212 KB Output is correct
9 Correct 17 ms 5212 KB Output is correct
10 Correct 224 ms 21900 KB Output is correct
11 Correct 226 ms 21692 KB Output is correct
12 Correct 236 ms 26492 KB Output is correct
13 Correct 143 ms 21700 KB Output is correct
14 Correct 141 ms 21132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 24008 KB Output is correct
2 Correct 135 ms 23872 KB Output is correct
3 Correct 126 ms 25800 KB Output is correct
4 Correct 124 ms 25772 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4540 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 33 ms 5724 KB Output is correct
8 Correct 410 ms 27088 KB Output is correct
9 Correct 417 ms 27332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 27200 KB Output is correct
2 Correct 295 ms 26824 KB Output is correct
3 Correct 294 ms 27092 KB Output is correct
4 Correct 334 ms 27084 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 33 ms 5320 KB Output is correct
7 Correct 418 ms 22764 KB Output is correct
8 Correct 424 ms 27076 KB Output is correct
9 Correct 291 ms 22936 KB Output is correct
10 Correct 314 ms 22536 KB Output is correct
11 Correct 302 ms 25268 KB Output is correct
12 Correct 279 ms 25124 KB Output is correct
13 Correct 305 ms 27080 KB Output is correct