oj.uz

Submission #863667

# Submission time Handle Problem Language Result Execution time Memory
863667 2023-10-20T17:03:08 Z Mizo_Compiler Inside information (BOI21_servers) C++17
50 / 100
 138 ms 37884 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];
bool r[N];
vector<array<int, 3>> qr;
vector<pair<int, int>> adj[N];
vector<int> c[N], ar;
 
void upd(int i, int val) {
	i++;
	while (i <= n) {
		bit[i] += val;
		i += (i & -i);
	}
}
 
int get(int i) {
	i++;
	int ret = 0;
	while (i) {
		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);
	ar.pb(ls);
	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);
	}
	while (!ar.empty()) {
		upd(ar.back(), -1);
		ar.pop_back();
	}
	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;
	int cc = 0;
	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});
			cc++;
		} 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, cc});
		}
	}
	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 19 ms 14800 KB Output is correct
2 Correct 22 ms 14696 KB Output is correct
3 Correct 29 ms 14848 KB Output is correct
4 Correct 22 ms 14812 KB Output is correct
5 Correct 30 ms 15116 KB Output is correct
6 Correct 29 ms 14836 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14800 KB Output is correct
2 Correct 22 ms 14696 KB Output is correct
3 Correct 29 ms 14848 KB Output is correct
4 Correct 22 ms 14812 KB Output is correct
5 Correct 30 ms 15116 KB Output is correct
6 Correct 29 ms 14836 KB Output is correct
7 Incorrect 18 ms 14800 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14800 KB Output is correct
2 Correct 74 ms 28928 KB Output is correct
3 Correct 99 ms 29184 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14800 KB Output is correct
2 Correct 74 ms 28928 KB Output is correct
3 Correct 99 ms 29184 KB Output is correct
4 Incorrect 21 ms 15612 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14800 KB Output is correct
2 Correct 98 ms 37244 KB Output is correct
3 Correct 97 ms 37772 KB Output is correct
4 Correct 82 ms 37884 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14800 KB Output is correct
2 Correct 98 ms 37244 KB Output is correct
3 Correct 97 ms 37772 KB Output is correct
4 Correct 82 ms 37884 KB Output is correct
5 Incorrect 19 ms 15760 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14776 KB Output is correct
2 Correct 79 ms 28644 KB Output is correct
3 Correct 81 ms 29436 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14776 KB Output is correct
2 Correct 79 ms 28644 KB Output is correct
3 Correct 81 ms 29436 KB Output is correct
4 Incorrect 19 ms 15572 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14912 KB Output is correct
2 Correct 97 ms 37116 KB Output is correct
3 Correct 81 ms 37744 KB Output is correct
4 Correct 80 ms 37700 KB Output is correct
5 Correct 20 ms 15776 KB Output is correct
6 Correct 89 ms 28924 KB Output is correct
7 Correct 81 ms 29400 KB Output is correct
8 Correct 93 ms 29692 KB Output is correct
9 Correct 87 ms 29952 KB Output is correct
10 Correct 87 ms 34560 KB Output is correct
11 Correct 108 ms 33584 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14912 KB Output is correct
2 Correct 97 ms 37116 KB Output is correct
3 Correct 81 ms 37744 KB Output is correct
4 Correct 80 ms 37700 KB Output is correct
5 Correct 20 ms 15776 KB Output is correct
6 Correct 89 ms 28924 KB Output is correct
7 Correct 81 ms 29400 KB Output is correct
8 Correct 93 ms 29692 KB Output is correct
9 Correct 87 ms 29952 KB Output is correct
10 Correct 87 ms 34560 KB Output is correct
11 Correct 108 ms 33584 KB Output is correct
12 Incorrect 18 ms 15564 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14704 KB Output is correct
2 Correct 22 ms 14816 KB Output is correct
3 Correct 33 ms 14848 KB Output is correct
4 Correct 22 ms 14816 KB Output is correct
5 Correct 31 ms 15240 KB Output is correct
6 Correct 29 ms 14824 KB Output is correct
7 Correct 31 ms 14788 KB Output is correct
8 Correct 100 ms 28924 KB Output is correct
9 Correct 114 ms 28924 KB Output is correct
10 Correct 19 ms 15604 KB Output is correct
11 Correct 113 ms 37484 KB Output is correct
12 Correct 90 ms 37632 KB Output is correct
13 Correct 104 ms 37284 KB Output is correct
14 Correct 22 ms 15564 KB Output is correct
15 Correct 79 ms 28932 KB Output is correct
16 Correct 108 ms 29668 KB Output is correct
17 Correct 117 ms 29884 KB Output is correct
18 Correct 108 ms 29968 KB Output is correct
19 Correct 102 ms 34684 KB Output is correct
20 Correct 138 ms 33808 KB Output is correct
21 Correct 125 ms 29396 KB Output is correct
22 Correct 104 ms 29284 KB Output is correct
23 Correct 86 ms 29456 KB Output is correct
24 Correct 95 ms 29412 KB Output is correct
25 Correct 110 ms 31136 KB Output is correct
26 Correct 110 ms 28980 KB Output is correct
27 Correct 95 ms 29188 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14704 KB Output is correct
2 Correct 22 ms 14816 KB Output is correct
3 Correct 33 ms 14848 KB Output is correct
4 Correct 22 ms 14816 KB Output is correct
5 Correct 31 ms 15240 KB Output is correct
6 Correct 29 ms 14824 KB Output is correct
7 Correct 31 ms 14788 KB Output is correct
8 Correct 100 ms 28924 KB Output is correct
9 Correct 114 ms 28924 KB Output is correct
10 Correct 19 ms 15604 KB Output is correct
11 Correct 113 ms 37484 KB Output is correct
12 Correct 90 ms 37632 KB Output is correct
13 Correct 104 ms 37284 KB Output is correct
14 Correct 22 ms 15564 KB Output is correct
15 Correct 79 ms 28932 KB Output is correct
16 Correct 108 ms 29668 KB Output is correct
17 Correct 117 ms 29884 KB Output is correct
18 Correct 108 ms 29968 KB Output is correct
19 Correct 102 ms 34684 KB Output is correct
20 Correct 138 ms 33808 KB Output is correct
21 Correct 125 ms 29396 KB Output is correct
22 Correct 104 ms 29284 KB Output is correct
23 Correct 86 ms 29456 KB Output is correct
24 Correct 95 ms 29412 KB Output is correct
25 Correct 110 ms 31136 KB Output is correct
26 Correct 110 ms 28980 KB Output is correct
27 Correct 95 ms 29188 KB Output is correct
28 Incorrect 23 ms 15612 KB Extra information in the output file
29 Halted 0 ms 0 KB -