oj.uz

Submission #957476

# Submission time Handle Problem Language Result Execution time Memory
957476 2024-04-03T20:45:28 Z Mizo_Compiler Synchronization (JOI13_synchronization) C++17
100 / 100
 411 ms 60308 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int32_t(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 2e5+1;
int n, m, q, p[N][18], cur = 0, par[N], sz[N], idx[N];
vector<int> adj[N], edg[(1 << 19)];
vector<pair<int, int>> ed;
bool vis[int(2e5)], qr[N];
ll ans[N], tk[N];
vector<pair<int, int>> vv;

int findp(int u) {
	return (par[u] == u ? u : findp(par[u]));
}

void merge(int u, int v) {
	u = findp(u), v = findp(v);
	if (u == v)return;
	cur++;
	if (sz[u] < sz[v])swap(u, v);
	sz[u] += sz[v];
	par[v] = u;
	vv.pb({u, v});
}

void rollback(int tm) {
	while (cur > tm) {
		par[vv.back().S] = vv.back().S;
		sz[vv.back().F] -= sz[vv.back().S];
		vv.pop_back();
		cur--;
	}
}

void dfs(int u) {
	for (auto &v : adj[u]) {
		if (v == p[u][0])continue;
		p[v][0] = u;
		for (int i = 1; i < 18; i++) {
			p[v][i] = p[p[v][i-1]][i-1];
		}
		dfs(v);
	}
}

void upd(int li, int ri, int x, int l, int r, int id) {
	if (li >= l && ri <= r) {
		edg[x].pb(id);
		return;
	}
	if (li > r || ri < l)return;
	int mid = (li + ri) >> 1;
	upd(li, mid, x*2+1, l, r, id);
	upd(mid+1, ri, x*2+2, l, r, id);
}

int getp(int u) {
	int x = findp(u);
	for (int i = 17; i >= 0; i--) {
		if (findp(p[u][i]) == x) {
			u = p[u][i];
		}
	}
	return u;
}

void sol(int i) {
	int u = ed[idx[i]].F, v = ed[idx[i]].S;
	int rt = getp(u);
	if (qr[i]) {
		ans[rt] += ans[v] - tk[v];
		tk[v] = ans[v];
	} else {
		ans[v] = ans[rt];
		tk[v] = ans[v];
	}
}

void walk(int l, int r, int x) {
	int tmp = cur;
	for (auto &i : edg[x]) {
		merge(ed[i].F, ed[i].S);
	}
	if (l == r) {
		sol(l);
		rollback(tmp);
		return;
	}
	int mid = (l + r) >> 1;
	walk(l, mid, x*2+1);
	walk(mid+1, r, x*2+2);
	rollback(tmp);
	return;
}

signed main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> q;
	for (int i = 0; i+1 < n; i++) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
		ed.pb({u, v});
		ans[i] = 1;
		sz[i] = 1;
		par[i] = i;
	}
	sz[n-1] = ans[n-1] = 1;
	par[n-1] = n-1;
	dfs(0);
	for (int i = 0; i+1 < n; i++) {
		if (p[ed[i].F][0] == ed[i].S) {
			swap(ed[i].F, ed[i].S);
		}
	}
	map<int, int> mp;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		--x;
		vis[x] ^= 1;
		if (vis[x])mp[x] = i;
		else upd(0, m-1, 0, mp[x], i-1, x), mp.erase(x);
		qr[i] = vis[x];
		idx[i] = x;
	}
	for (auto &[x, y] : mp) {
		upd(0, m-1, 0, y, m-1, x);
	}
	walk(0, m-1, 0);
	for (auto &[x, y] : mp) {
		merge(ed[x].F, ed[x].S);
	}
	while (q--) {
		int u;
		cin >> u;
		--u;
		cout << ans[getp(u)] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 4 ms 22988 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 7 ms 23128 KB Output is correct
5 Correct 5 ms 22876 KB Output is correct
6 Correct 6 ms 23132 KB Output is correct
7 Correct 25 ms 25688 KB Output is correct
8 Correct 26 ms 25692 KB Output is correct
9 Correct 25 ms 25640 KB Output is correct
10 Correct 333 ms 53064 KB Output is correct
11 Correct 382 ms 54760 KB Output is correct
12 Correct 327 ms 59320 KB Output is correct
13 Correct 251 ms 54632 KB Output is correct
14 Correct 204 ms 49348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 53716 KB Output is correct
2 Correct 129 ms 55048 KB Output is correct
3 Correct 106 ms 53936 KB Output is correct
4 Correct 109 ms 53960 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22872 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 5 ms 22872 KB Output is correct
6 Correct 6 ms 23128 KB Output is correct
7 Correct 29 ms 26192 KB Output is correct
8 Correct 411 ms 58648 KB Output is correct
9 Correct 337 ms 60308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 58760 KB Output is correct
2 Correct 127 ms 54360 KB Output is correct
3 Correct 130 ms 54684 KB Output is correct
4 Correct 129 ms 54600 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 5 ms 22872 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 5 ms 22872 KB Output is correct
5 Correct 7 ms 23132 KB Output is correct
6 Correct 27 ms 25728 KB Output is correct
7 Correct 387 ms 53960 KB Output is correct
8 Correct 348 ms 60308 KB Output is correct
9 Correct 280 ms 55928 KB Output is correct
10 Correct 215 ms 50200 KB Output is correct
11 Correct 152 ms 56008 KB Output is correct
12 Correct 160 ms 55872 KB Output is correct
13 Correct 137 ms 54736 KB Output is correct