oj.uz

Submission #1072992

# Submission time Handle Problem Language Result Execution time Memory
1072992 2024-08-24T08:06:20 Z pubin06 Synchronization (JOI13_synchronization) C++14
100 / 100
 408 ms 21768 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;

const int MXn = 100005;

int n, m, q;
pair<int, int> e[MXn];
vector<int> adj[MXn];
int up0[MXn], sz[MXn];
void DFS(int u, int par) {
	sz[u] = 1;
	for (int v: adj[u]) if (v != par) {
		up0[v] = u;
		DFS(v, u);
		sz[u] += sz[v];
	}
}
int head[MXn], st[MXn], timer = 0, ord[MXn];
void HLD(int u, int par, int he) {
	st[u] = ++timer;
	ord[st[u]] = u;
	head[u] = he;
	pair<int, int> best = {-1, -1};
	for (int v: adj[u]) if (v != par) {
		best = max(best, {sz[v], v});
	}
	if (best.se > 0) {
		HLD(best.se, u, he);
		for (int v: adj[u]) if (v != par && v != best.se) {
			HLD(v, u, v);
		}
	}
}

int ST[1 << 18] = {0};
void update(int i) {
	int id = 1, l = 1, r = n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (i <= mid) {
			id <<= 1;
			r = mid;
		} else {
			id = id << 1 | 1;
			l = mid + 1;
		}
	}
	ST[id] ^= 1;
	while (id > 1) {
		id >>= 1;
		ST[id] = min(ST[id << 1], ST[id << 1 | 1]);
	}
}
int get(int Lf, int Rt, int id = 1, int l = 1, int r = n) {
	if (Lf <= l && r <= Rt) return ST[id];
	int mid = (l + r) >> 1, res = 1;
	if (Lf <= mid) res = min(res, get(Lf, Rt, id << 1, l, mid));
	if (mid < Rt) res = min(res, get(Lf, Rt, id << 1 | 1, mid + 1, r));
	return res;
}

int mark[MXn] = {0};
int find(int u) {
	// int cc = u;
	// if (cc == 5) cerr << "[";
	while (mark[u]) {
		if (get(st[head[u]], st[u])) {
			u = head[u];
			// if (cc == 5) cerr << "0" << u << ' ';
		} else {
			int pos = 0;
			int l = st[head[u]], r = st[u], mid;
			while (l <= r) {
				mid = (l + r) >> 1;
				if (get(mid, st[u])) {
					pos = mid;
					r = mid - 1;
				} else l = mid + 1;
			}
			u = ord[pos];
			// if (cc == 5) cerr << "00" << u << ' ';
		}
		u = up0[u];
	}
	// if (cc == 5) cerr << "]";
	return u;
}
int ans[MXn], last[MXn]; // last[id] là số thông tin mà tplt chứa cạnh thứ id có, tính đến thời điểm cuối cùng đến hiện tại nó còn được nối

signed main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> q;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
		e[i] = {u, v};
	}
	DFS(1, 0);
	HLD(1, 0, 1);
	// for (int i = 1; i <= n; i++) cerr << head[i] << ' ';
	// cerr << '\n';
	// for (int i = 1; i <= n; i++) cerr << st[i] << ' ';
	// cerr << '\n';
	// cerr << '\n';
	
	for (int u = 1; u <= n; u++) ans[u] = 1;
	while (m--) {
		int id; cin >> id;
		if (up0[e[id].fi] == e[id].se) swap(e[id].fi, e[id].se);
		if (!mark[e[id].se]) {
			ans[find(e[id].fi)] += ans[e[id].se] - last[id];
		} else {
			ans[e[id].se] = last[id] = ans[find(e[id].fi)];
		}
		mark[e[id].se] ^= 1;
		update(st[e[id].se]);
		// for (int i = 1; i <= n; i++) cerr << find(i) << ' ';
		// cerr << '\n';
	}
	for (int i = 1; i <= n; i++) ans[i] = ans[find(i)];
	while (q--) {
		int u; cin >> u; cout << ans[u] << '\n';
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2784 KB Output is correct
5 Correct 1 ms 2612 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 10 ms 3740 KB Output is correct
8 Correct 10 ms 3676 KB Output is correct
9 Correct 10 ms 3676 KB Output is correct
10 Correct 120 ms 13108 KB Output is correct
11 Correct 115 ms 13152 KB Output is correct
12 Correct 339 ms 20972 KB Output is correct
13 Correct 63 ms 13000 KB Output is correct
14 Correct 152 ms 12372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 16724 KB Output is correct
2 Correct 358 ms 16724 KB Output is correct
3 Correct 341 ms 19864 KB Output is correct
4 Correct 340 ms 19952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 23 ms 4700 KB Output is correct
8 Correct 338 ms 21616 KB Output is correct
9 Correct 340 ms 21584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 21732 KB Output is correct
2 Correct 388 ms 21076 KB Output is correct
3 Correct 358 ms 21076 KB Output is correct
4 Correct 349 ms 21072 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 12 ms 3928 KB Output is correct
7 Correct 133 ms 14276 KB Output is correct
8 Correct 336 ms 21768 KB Output is correct
9 Correct 75 ms 14280 KB Output is correct
10 Correct 153 ms 13396 KB Output is correct
11 Correct 408 ms 17660 KB Output is correct
12 Correct 401 ms 17920 KB Output is correct
13 Correct 354 ms 21072 KB Output is correct