oj.uz

Submission #764580

# Submission time Handle Problem Language Result Execution time Memory
764580 2023-06-23T15:58:36 Z NK_ Synchronization (JOI13_synchronization) C++17
100 / 100
 1599 ms 13300 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;

struct DSU {
	V<int> e, ans; V<AR<int, 2>> last; V<AR<int, 5>> his; 
	void init(int N) { e = V<int>(N, -1); ans = V<int>(N, 1); last = V<AR<int, 2>>(N, {0, 0}); his = {}; }
	int get(int x) { return e[x] < 0 ? x : get(e[x]); }
	int info(int x) { return ans[get(x)]; }
	void upd(int x, int y, int i) {
		int dx = ans[y] - last[i][0];
		int dy = ans[x] - last[i][1];
		ans[x] += dx, ans[y] += dy;
		last[i] = {ans[x], ans[y]};
	}
	void unite(int x, int y, int i) {
		x = get(x), y = get(y); assert(x != y);
		upd(x, y, i);
		if (e[x] > e[y]) swap(x, y);
		his.pb({x, e[x], y, e[y], i});
		e[x] += e[y]; e[y] = x;
	} 
	int rollback() {
		if (sz(his) == 0) return -1;
		auto [x, ex, y, ey, i] = his.back(); his.pop_back();
		e[x] = ex, e[y] = ey;
		upd(x, y, i);
		return i;
	}
};

const int BLK = 750;
const int INF = int(1e9) + 10;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, Q; cin >> N >> M >> Q;

	V<AR<int, 2>> E(N-1);
	for(int e = 0; e < N-1; e++) {
		int u, v; cin >> u >> v; --u, --v;
		E[e] = {u, v};
	}

	DSU D; D.init(N);

	V<V<AR<int, 2>>> EV(N);
	V<int> T(M);
	for(int i = 0; i < M; i++) {
		int x; cin >> x; --x;
		T[i] = x;
		EV[x].pb({i, sz(EV[x]) % 2});
	}

	for(int i = 0; i < N; i++) {
		EV[i].pb({INF + i, -1});
		reverse(begin(EV[i]), end(EV[i]));
	}

	V<int> ed; set<int> ex;
	auto rebuild = [&]() {
		ed = {};
		
		while(1) {
			int r = D.rollback();
			if (r == -1) break;
			else ed.pb(r);
		}

		sort(begin(ed), end(ed), [&](int x, int y) {
			return EV[x].back()[0] < EV[y].back()[0];
		});

		reverse(begin(ed), end(ed));
		for(const auto &e : ed) D.unite(E[e][0], E[e][1], e);
	};

	auto rem = [&](int x) {
		ed = {};

		while(1) {
			int r = D.rollback();
			if (r == x) break;
			else ed.pb(r);
		}

		for(const auto &e : ed) D.unite(E[e][0], E[e][1], e);
	};	
		
	for(int i = 0; i < M; i++) {
		int e = T[i], t = EV[e].back()[1]; EV[e].pop_back();

		if (t == 0) {
			ex.insert(e);
			D.unite(E[e][0], E[e][1], e);
		} else {
			rem(e);
			if (ex.find(e) != ex.end()) ex.erase(e);
		}

		if (sz(ex) >= BLK) {
			rebuild();
			ex = {};
		}
	}

	rem(-1);

	while(Q--) {
		int u; cin >> u; --u;
		cout << D.ans[u] << nl;
	}


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 58 ms 1624 KB Output is correct
8 Correct 56 ms 1536 KB Output is correct
9 Correct 56 ms 1628 KB Output is correct
10 Correct 1576 ms 12228 KB Output is correct
11 Correct 1599 ms 12260 KB Output is correct
12 Correct 1544 ms 12212 KB Output is correct
13 Correct 1518 ms 12328 KB Output is correct
14 Correct 943 ms 11612 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 12844 KB Output is correct
2 Correct 617 ms 12632 KB Output is correct
3 Correct 766 ms 11664 KB Output is correct
4 Correct 789 ms 11628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 55 ms 1632 KB Output is correct
8 Correct 1412 ms 12388 KB Output is correct
9 Correct 1423 ms 12284 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1592 ms 12252 KB Output is correct
2 Correct 757 ms 12028 KB Output is correct
3 Correct 738 ms 12028 KB Output is correct
4 Correct 743 ms 11944 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 57 ms 1628 KB Output is correct
7 Correct 1531 ms 12392 KB Output is correct
8 Correct 1452 ms 12312 KB Output is correct
9 Correct 1545 ms 12688 KB Output is correct
10 Correct 988 ms 12176 KB Output is correct
11 Correct 613 ms 13300 KB Output is correct
12 Correct 611 ms 13144 KB Output is correct
13 Correct 743 ms 12036 KB Output is correct