oj.uz

답안 #863523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
863523 2023-10-20T14:05:11 Z Mizo_Compiler Inside information (BOI21_servers) C++17
50 / 100
 142 ms 30460 KB 
#include <bits/stdc++.h>
using namespace std;
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 = 120005;
int n, pr[N], sz[N], q, dep[N], p[N][17], mn[N], vt[N];
int mx[N];
vector<array<int, 3>> qr;
vector<pair<int, int>> adj[N];
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 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;
	}
	int cc = 0;
	q += n-1;
	for (int i = 0; i < q; i++) {
		char c;
		cin >> c;
		if (c == '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 (c == 'Q') {
			int u, v;
			cin >> u >> v;
			--u, --v;
			qr.pb({1, u, v});
		} else {
			int u;
			cin >> u;
			--u;
			qr.pb({2, u, cc});
		}
	}
	vt[0] = q+5;
	init(0, 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 << v+1 << "\n";
		}
	}
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 6608 KB Output is correct
2 Correct 21 ms 8672 KB Output is correct
3 Correct 27 ms 8952 KB Output is correct
4 Correct 21 ms 8928 KB Output is correct
5 Correct 34 ms 9216 KB Output is correct
6 Correct 32 ms 8684 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 6608 KB Output is correct
2 Correct 21 ms 8672 KB Output is correct
3 Correct 27 ms 8952 KB Output is correct
4 Correct 21 ms 8928 KB Output is correct
5 Correct 34 ms 9216 KB Output is correct
6 Correct 32 ms 8684 KB Output is correct
7 Incorrect 22 ms 6608 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6604 KB Output is correct
2 Correct 98 ms 21776 KB Output is correct
3 Correct 117 ms 21764 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6604 KB Output is correct
2 Correct 98 ms 21776 KB Output is correct
3 Correct 117 ms 21764 KB Output is correct
4 Incorrect 23 ms 6860 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6676 KB Output is correct
2 Correct 92 ms 30460 KB Output is correct
3 Correct 105 ms 30440 KB Output is correct
4 Correct 108 ms 30272 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6676 KB Output is correct
2 Correct 92 ms 30460 KB Output is correct
3 Correct 105 ms 30440 KB Output is correct
4 Correct 108 ms 30272 KB Output is correct
5 Incorrect 16 ms 6444 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6508 KB Output is correct
2 Correct 77 ms 22020 KB Output is correct
3 Correct 118 ms 22504 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6508 KB Output is correct
2 Correct 77 ms 22020 KB Output is correct
3 Correct 118 ms 22504 KB Output is correct
4 Incorrect 16 ms 6604 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 6608 KB Output is correct
2 Correct 80 ms 30400 KB Output is correct
3 Correct 98 ms 30376 KB Output is correct
4 Correct 78 ms 30408 KB Output is correct
5 Correct 18 ms 6608 KB Output is correct
6 Correct 75 ms 21760 KB Output is correct
7 Correct 86 ms 22268 KB Output is correct
8 Correct 142 ms 22700 KB Output is correct
9 Correct 99 ms 22836 KB Output is correct
10 Correct 106 ms 27172 KB Output is correct
11 Correct 132 ms 26428 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 6608 KB Output is correct
2 Correct 80 ms 30400 KB Output is correct
3 Correct 98 ms 30376 KB Output is correct
4 Correct 78 ms 30408 KB Output is correct
5 Correct 18 ms 6608 KB Output is correct
6 Correct 75 ms 21760 KB Output is correct
7 Correct 86 ms 22268 KB Output is correct
8 Correct 142 ms 22700 KB Output is correct
9 Correct 99 ms 22836 KB Output is correct
10 Correct 106 ms 27172 KB Output is correct
11 Correct 132 ms 26428 KB Output is correct
12 Incorrect 19 ms 6604 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6608 KB Output is correct
2 Correct 21 ms 8632 KB Output is correct
3 Correct 30 ms 8952 KB Output is correct
4 Correct 27 ms 8828 KB Output is correct
5 Correct 37 ms 9196 KB Output is correct
6 Correct 29 ms 8948 KB Output is correct
7 Correct 18 ms 6608 KB Output is correct
8 Correct 95 ms 21848 KB Output is correct
9 Correct 110 ms 21980 KB Output is correct
10 Correct 18 ms 6608 KB Output is correct
11 Correct 103 ms 30424 KB Output is correct
12 Correct 106 ms 30388 KB Output is correct
13 Correct 102 ms 30356 KB Output is correct
14 Correct 19 ms 6608 KB Output is correct
15 Correct 76 ms 21760 KB Output is correct
16 Correct 94 ms 22264 KB Output is correct
17 Correct 112 ms 22800 KB Output is correct
18 Correct 101 ms 22896 KB Output is correct
19 Correct 91 ms 27116 KB Output is correct
20 Correct 133 ms 26648 KB Output is correct
21 Correct 78 ms 21900 KB Output is correct
22 Correct 79 ms 22012 KB Output is correct
23 Correct 82 ms 22372 KB Output is correct
24 Correct 85 ms 22332 KB Output is correct
25 Correct 88 ms 24132 KB Output is correct
26 Correct 81 ms 21756 KB Output is correct
27 Correct 77 ms 21756 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6608 KB Output is correct
2 Correct 21 ms 8632 KB Output is correct
3 Correct 30 ms 8952 KB Output is correct
4 Correct 27 ms 8828 KB Output is correct
5 Correct 37 ms 9196 KB Output is correct
6 Correct 29 ms 8948 KB Output is correct
7 Correct 18 ms 6608 KB Output is correct
8 Correct 95 ms 21848 KB Output is correct
9 Correct 110 ms 21980 KB Output is correct
10 Correct 18 ms 6608 KB Output is correct
11 Correct 103 ms 30424 KB Output is correct
12 Correct 106 ms 30388 KB Output is correct
13 Correct 102 ms 30356 KB Output is correct
14 Correct 19 ms 6608 KB Output is correct
15 Correct 76 ms 21760 KB Output is correct
16 Correct 94 ms 22264 KB Output is correct
17 Correct 112 ms 22800 KB Output is correct
18 Correct 101 ms 22896 KB Output is correct
19 Correct 91 ms 27116 KB Output is correct
20 Correct 133 ms 26648 KB Output is correct
21 Correct 78 ms 21900 KB Output is correct
22 Correct 79 ms 22012 KB Output is correct
23 Correct 82 ms 22372 KB Output is correct
24 Correct 85 ms 22332 KB Output is correct
25 Correct 88 ms 24132 KB Output is correct
26 Correct 81 ms 21756 KB Output is correct
27 Correct 77 ms 21756 KB Output is correct
28 Incorrect 16 ms 6608 KB Extra information in the output file
29 Halted 0 ms 0 KB -