oj.uz

Submission #764579

# Submission time Handle Problem Language Result Execution time Memory
764579 2023-06-23T15:58:14 Z NK_ Synchronization (JOI13_synchronization) C++17
100 / 100
 2118 ms 15844 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 = 500;
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;
		// cout << x << " " << sz(EV[x]) << endl;
		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];
		});

		// cout << "FIRST: " << ed[0] << endl;

		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();
		// cout << "EX: " << ex << endl;

		if (t == 0) {
			ex.insert(e);
			D.unite(E[e][0], E[e][1], e);
			// cout << "ADD: " << e << endl;
		} 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 1 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 460 KB Output is correct
7 Correct 44 ms 1720 KB Output is correct
8 Correct 42 ms 1736 KB Output is correct
9 Correct 42 ms 1736 KB Output is correct
10 Correct 1863 ms 13764 KB Output is correct
11 Correct 1855 ms 14560 KB Output is correct
12 Correct 1696 ms 14568 KB Output is correct
13 Correct 1827 ms 14204 KB Output is correct
14 Correct 1474 ms 13420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1080 ms 12820 KB Output is correct
2 Correct 996 ms 14716 KB Output is correct
3 Correct 1251 ms 12424 KB Output is correct
4 Correct 1239 ms 12624 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 1 ms 212 KB Output is correct
3 Correct 1 ms 316 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 468 KB Output is correct
7 Correct 43 ms 1868 KB Output is correct
8 Correct 1827 ms 15192 KB Output is correct
9 Correct 1852 ms 15184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1902 ms 12328 KB Output is correct
2 Correct 1226 ms 14152 KB Output is correct
3 Correct 1363 ms 14344 KB Output is correct
4 Correct 1212 ms 14324 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 75 ms 1864 KB Output is correct
7 Correct 2118 ms 13296 KB Output is correct
8 Correct 1831 ms 15200 KB Output is correct
9 Correct 1899 ms 15180 KB Output is correct
10 Correct 1762 ms 14432 KB Output is correct
11 Correct 1091 ms 15800 KB Output is correct
12 Correct 1058 ms 15844 KB Output is correct
13 Correct 1295 ms 14272 KB Output is correct