oj.uz

Submission #863623

# Submission time Handle Problem Language Result Execution time Memory
863623 2023-10-20T15:51:32 Z Mizo_Compiler Inside information (BOI21_servers) C++17
55 / 100
 3500 ms 38088 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 120001;
int n, pr[N], sz[N], q, dep[N], p[N][17], mn[N], vt[N];
int mx[N], sze[N], bit[N+N], ans[N+N], ls[N+N], vid = 0;
bool r[N];
vector<array<int, 3>> qr;
vector<pair<int, int>> adj[N];
vector<int> c[N];

void upd(int i, int val) {
	i++;
	while (i <= n+q) {
		if (ls[i] != vid) {
			ls[i] = vid;
			bit[i] = 0;
		}
		bit[i] += val;
		i += (i & -i);
	}
}

int get(int i) {
	i++;
	int ret = 0;
	while (i) {
		if (ls[i] != vid) {
			ls[i] = vid;
			bit[i] = 0;
		}
		ret += bit[i];
		i -= (i & -i);
	}
	return ret;
}

void dfs_sz(int u, int par) {
	sze[u] = 1;
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		dfs_sz(v, u);
		sze[u] += sz[v];
	}
}

int centroid(int u, int par, int mxsz) {
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		if (2*sze[v] > mxsz)return centroid(v, u, mxsz);
	}
	return u;
}

int findp(int u) {
	return pr[u] = (pr[u] == u ? u : findp(pr[u]));
}
 
void merge(int u, int v) {
	u = findp(u), v = findp(v);
	if (u == v)return;
	if (sz[u] < sz[v])swap(u, v);
	sz[u] += sz[v];
	pr[v] = u;
}
 
void init(int u, int par) {
	for (auto &[v, t] : adj[u]) {
		if (v == par)continue;
		p[v][0] = u;
		dep[v] = dep[u]+1;
		vt[v] = t;
		mn[v] = (vt[v] < vt[u] ? mn[u] : u);
		mx[v] = (vt[v] > vt[u] ? mx[u] : u);
		for (int i = 1; i < 17; i++) {
			p[v][i] = p[p[v][i-1]][i-1];
		}
		init(v, u);
	}
}
 
int lift(int u, int k) {
	for (int i = 0; i < 17; i++) {
		if ((k & (1 << i)))u = p[u][i];
	}
	return u;
}
 
int lca(int u, int v) {
	if (dep[u] < dep[v])swap(u, v);
	u = lift(u, dep[u]-dep[v]);
	if (u == v)return u;
	for (int i = 16; i >= 0; i--) {
		if (p[u][i] != p[v][i]) {
			u = p[u][i];
			v = p[v][i];
		}
	}
	return p[u][0];
}
 
bool sol(int u, int v) {
	if (findp(u) != findp(v))return false;
	int l = lca(u, v);
	if (dep[mx[u]] > dep[l])return false;
	if (dep[mn[v]] > dep[l])return false;
	if (l == v || l == u)return true;
	u = lift(u, dep[u]-dep[l]-1);
	v = lift(v, dep[v]-dep[l]-1);
	return (vt[v] < vt[u]);
}
int vv;
void dfs(int u, int par, int ls) {
	for (auto &t : c[u]) {
		ans[t] += get(t) + (vv <= t);
	}
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		if (t > ls)continue;
		dfs(v, u, t);
	}
}

void dfs2(int u, int par, int ls) {
	upd(ls, 1);
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		if (t < ls)continue;
		dfs2(v, u, t);
	}
}

void cen(int u) {
	dfs_sz(u, u);
	u = centroid(u, u, sze[u]);
	for (auto &[v, t] : adj[u]) {
		if (r[v])continue;
		vv = t;
		dfs(v, u, t);
		dfs2(v, u, t);
	}
	for (auto &t : c[u]) {
		ans[t] += get(t);
	}
	vid++;
	r[u] = true;
	for (auto &[v, t] : adj[u]) {
		if (r[v])continue;
		cen(v);
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		pr[i] = i, sz[i] = 1;
	}
	q += n-1;
	bool ff = true;
	for (int i = 0; i < q; i++) {
		char ch;
		cin >> ch;
		if (ch == 'S') {
			int u, v;
			cin >> u >> v;
			--u, --v;
			qr.pb({0, u, v});
			adj[u].pb({v, i});
			adj[v].pb({u, i});
		} else if (ch == 'Q') {
			int u, v;
			cin >> u >> v;
			--u, --v;
			qr.pb({1, u, v});
		} else {
			ff = false;
			int u;
			cin >> u;
			--u;
			c[u].pb(i);
			qr.pb({2, u, i});
		}
	}
	vt[0] = q+5;
	init(0, 0);
	if (!ff) {
		for (int i = 0; i < n; i++)reverse(all(adj[i]));
		cen(0);
	}
	for (auto &[op, u, v] : qr) {
		if (!op) {
			merge(u, v);
		}
		else if (op == 1) {
			cout << (sol(u, v) ? "yes\n" : "no\n");
		} else {
			cout << ans[v] + 1 << "\n";
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12752 KB Output is correct
2 Correct 21 ms 12764 KB Output is correct
3 Correct 29 ms 13020 KB Output is correct
4 Correct 21 ms 12972 KB Output is correct
5 Correct 30 ms 13304 KB Output is correct
6 Correct 29 ms 12780 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12752 KB Output is correct
2 Correct 21 ms 12764 KB Output is correct
3 Correct 29 ms 13020 KB Output is correct
4 Correct 21 ms 12972 KB Output is correct
5 Correct 30 ms 13304 KB Output is correct
6 Correct 29 ms 12780 KB Output is correct
7 Correct 19 ms 13524 KB Output is correct
8 Correct 44 ms 14340 KB Output is correct
9 Correct 29 ms 15372 KB Output is correct
10 Correct 144 ms 14388 KB Output is correct
11 Correct 128 ms 14596 KB Output is correct
12 Correct 28 ms 15376 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12748 KB Output is correct
2 Correct 74 ms 25980 KB Output is correct
3 Correct 99 ms 25988 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12748 KB Output is correct
2 Correct 74 ms 25980 KB Output is correct
3 Correct 99 ms 25988 KB Output is correct
4 Correct 20 ms 13524 KB Output is correct
5 Correct 86 ms 28412 KB Output is correct
6 Correct 91 ms 28432 KB Output is correct
7 Correct 82 ms 28824 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12752 KB Output is correct
2 Correct 82 ms 34560 KB Output is correct
3 Correct 91 ms 34604 KB Output is correct
4 Correct 80 ms 34556 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12752 KB Output is correct
2 Correct 82 ms 34560 KB Output is correct
3 Correct 91 ms 34604 KB Output is correct
4 Correct 80 ms 34556 KB Output is correct
5 Correct 20 ms 13268 KB Output is correct
6 Execution timed out 3531 ms 37652 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12748 KB Output is correct
2 Correct 71 ms 26108 KB Output is correct
3 Correct 79 ms 26608 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12748 KB Output is correct
2 Correct 71 ms 26108 KB Output is correct
3 Correct 79 ms 26608 KB Output is correct
4 Correct 21 ms 13264 KB Output is correct
5 Execution timed out 3562 ms 29592 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 88 ms 34552 KB Output is correct
3 Correct 79 ms 34616 KB Output is correct
4 Correct 88 ms 34500 KB Output is correct
5 Correct 24 ms 12776 KB Output is correct
6 Correct 74 ms 26368 KB Output is correct
7 Correct 82 ms 26652 KB Output is correct
8 Correct 102 ms 26860 KB Output is correct
9 Correct 87 ms 26888 KB Output is correct
10 Correct 88 ms 31488 KB Output is correct
11 Correct 132 ms 30784 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 88 ms 34552 KB Output is correct
3 Correct 79 ms 34616 KB Output is correct
4 Correct 88 ms 34500 KB Output is correct
5 Correct 24 ms 12776 KB Output is correct
6 Correct 74 ms 26368 KB Output is correct
7 Correct 82 ms 26652 KB Output is correct
8 Correct 102 ms 26860 KB Output is correct
9 Correct 87 ms 26888 KB Output is correct
10 Correct 88 ms 31488 KB Output is correct
11 Correct 132 ms 30784 KB Output is correct
12 Correct 19 ms 13268 KB Output is correct
13 Execution timed out 3537 ms 38024 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12752 KB Output is correct
2 Correct 21 ms 12768 KB Output is correct
3 Correct 29 ms 13056 KB Output is correct
4 Correct 20 ms 13020 KB Output is correct
5 Correct 30 ms 13148 KB Output is correct
6 Correct 29 ms 12784 KB Output is correct
7 Correct 20 ms 12752 KB Output is correct
8 Correct 73 ms 26108 KB Output is correct
9 Correct 78 ms 25988 KB Output is correct
10 Correct 17 ms 13004 KB Output is correct
11 Correct 86 ms 34472 KB Output is correct
12 Correct 79 ms 34996 KB Output is correct
13 Correct 78 ms 34492 KB Output is correct
14 Correct 18 ms 12748 KB Output is correct
15 Correct 80 ms 26112 KB Output is correct
16 Correct 78 ms 26552 KB Output is correct
17 Correct 100 ms 26952 KB Output is correct
18 Correct 96 ms 26968 KB Output is correct
19 Correct 91 ms 31536 KB Output is correct
20 Correct 107 ms 30640 KB Output is correct
21 Correct 79 ms 26108 KB Output is correct
22 Correct 113 ms 26044 KB Output is correct
23 Correct 96 ms 26692 KB Output is correct
24 Correct 82 ms 26624 KB Output is correct
25 Correct 132 ms 28400 KB Output is correct
26 Correct 78 ms 25852 KB Output is correct
27 Correct 86 ms 25956 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12752 KB Output is correct
2 Correct 21 ms 12768 KB Output is correct
3 Correct 29 ms 13056 KB Output is correct
4 Correct 20 ms 13020 KB Output is correct
5 Correct 30 ms 13148 KB Output is correct
6 Correct 29 ms 12784 KB Output is correct
7 Correct 20 ms 12752 KB Output is correct
8 Correct 73 ms 26108 KB Output is correct
9 Correct 78 ms 25988 KB Output is correct
10 Correct 17 ms 13004 KB Output is correct
11 Correct 86 ms 34472 KB Output is correct
12 Correct 79 ms 34996 KB Output is correct
13 Correct 78 ms 34492 KB Output is correct
14 Correct 18 ms 12748 KB Output is correct
15 Correct 80 ms 26112 KB Output is correct
16 Correct 78 ms 26552 KB Output is correct
17 Correct 100 ms 26952 KB Output is correct
18 Correct 96 ms 26968 KB Output is correct
19 Correct 91 ms 31536 KB Output is correct
20 Correct 107 ms 30640 KB Output is correct
21 Correct 79 ms 26108 KB Output is correct
22 Correct 113 ms 26044 KB Output is correct
23 Correct 96 ms 26692 KB Output is correct
24 Correct 82 ms 26624 KB Output is correct
25 Correct 132 ms 28400 KB Output is correct
26 Correct 78 ms 25852 KB Output is correct
27 Correct 86 ms 25956 KB Output is correct
28 Correct 19 ms 13264 KB Output is correct
29 Correct 43 ms 14340 KB Output is correct
30 Correct 32 ms 15368 KB Output is correct
31 Correct 134 ms 14344 KB Output is correct
32 Correct 128 ms 14608 KB Output is correct
33 Correct 27 ms 15368 KB Output is correct
34 Correct 20 ms 13524 KB Output is correct
35 Correct 92 ms 28412 KB Output is correct
36 Correct 66 ms 28488 KB Output is correct
37 Correct 81 ms 28928 KB Output is correct
38 Correct 18 ms 13268 KB Output is correct
39 Execution timed out 3522 ms 38088 KB Time limit exceeded
40 Halted 0 ms 0 KB -