Submission #863698

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
863698	2023-10-20T17:40:52 Z	TAhmed33	Inside information (BOI21_servers)	C++	15 / 100	3500 ms	30800 KB

servers

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120005;
const int MM = 19;
vector <pair <int, int>> adj[MAXN];
pair <int, int> queries[MAXN];
int t[MAXN];
int cnt = 0;
vector <int> pp[MAXN];
int dp[MM][MAXN];
int u[MAXN];
int dep[MAXN];
void calc (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j.first != par) {
			dep[j.first] = 1 + dep[pos];
			dp[0][j.first] = pos;
			u[j.first] = j.second;
			calc(j.first, pos);
		}
	}
}
int jump (int a, int b) {
	for (int i = MM - 1; i >= 0; i--) if (b & (1 << i)) a = dp[i][a];
	return a;
}
int lca (int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	b = jump(b, dep[b] - dep[a]);
	if (a == b) return a;
	for (int i = MM - 1; i >= 0; i--) {
		int x = dp[i][a], y = dp[i][b];
		if (x && y && x != y) {
			a = x; b = y;
		}
	}
	return dp[0][a];
}
int main () {
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int n, q;
	cin >> n >> q;
	int l = 0;
	for (int i = 1; i <= n + q - 1; i++) {
		char x;
		cin >> x;
		if (x == 'S') {
			cnt++;
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cnt});
			adj[b].push_back({a, cnt});
		} else {
			t[++l] = cnt;
			int a, b;
			cin >> a >> b;
			queries[l] = {a, b};
		}
	}
	calc(1, 0); 
	for (int i = 1; i < MM; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
	for (int i = 1; i <= l; i++) {
		vector <int> pp;
		int x = lca(queries[i].first, queries[i].second);
		int a = queries[i].first, b = queries[i].second;
		swap(a, b);
		vector <int> d;
		while (a != x) {
			d.push_back(u[a]);
			a = dp[0][a];
		}
		vector <int> g;
		while (b != x) {
			g.push_back(u[b]);
			b = dp[0][b];
		}
		reverse(g.begin(), g.end());
		for (auto j : g) d.push_back(j);
		bool flag = 1;
		for (int j = 1; j < (int)d.size(); j++) flag &= d[j] >= d[j - 1];
		if (!d.empty()) flag &= (d.back() <= t[i]);
		cout << (flag ? "yes\n" : "no\n");
	}
}

Subtask #1
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	17492 KB	Output is correct
2	Correct	96 ms	17516 KB	Output is correct
3	Correct	73 ms	17572 KB	Output is correct
4	Correct	439 ms	17740 KB	Output is correct
5	Correct	614 ms	18012 KB	Output is correct
6	Correct	68 ms	17560 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	17492 KB	Output is correct
2	Correct	96 ms	17516 KB	Output is correct
3	Correct	73 ms	17572 KB	Output is correct
4	Correct	439 ms	17740 KB	Output is correct
5	Correct	614 ms	18012 KB	Output is correct
6	Correct	68 ms	17560 KB	Output is correct
7	Runtime error	30 ms	30736 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	17492 KB	Output is correct
2	Correct	139 ms	22440 KB	Output is correct
3	Correct	134 ms	22200 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	17492 KB	Output is correct
2	Correct	139 ms	22440 KB	Output is correct
3	Correct	134 ms	22200 KB	Output is correct
4	Runtime error	34 ms	30640 KB	Execution killed with signal 11
5	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	17744 KB	Output is correct
2	Correct	170 ms	29892 KB	Output is correct
3	Correct	173 ms	29712 KB	Output is correct
4	Execution timed out	3574 ms	29940 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	17744 KB	Output is correct
2	Correct	170 ms	29892 KB	Output is correct
3	Correct	173 ms	29712 KB	Output is correct
4	Execution timed out	3574 ms	29940 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	17476 KB	Output is correct
2	Correct	167 ms	22356 KB	Output is correct
3	Correct	157 ms	22748 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	17476 KB	Output is correct
2	Correct	167 ms	22356 KB	Output is correct
3	Correct	157 ms	22748 KB	Output is correct
4	Runtime error	38 ms	30800 KB	Execution killed with signal 11
5	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	17384 KB	Output is correct
2	Correct	155 ms	30080 KB	Output is correct
3	Correct	155 ms	29752 KB	Output is correct
4	Execution timed out	3525 ms	30176 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	17384 KB	Output is correct
2	Correct	155 ms	30080 KB	Output is correct
3	Correct	155 ms	29752 KB	Output is correct
4	Execution timed out	3525 ms	30176 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	17488 KB	Output is correct
2	Correct	95 ms	17520 KB	Output is correct
3	Correct	70 ms	17748 KB	Output is correct
4	Correct	496 ms	18004 KB	Output is correct
5	Correct	611 ms	18260 KB	Output is correct
6	Correct	68 ms	17544 KB	Output is correct
7	Correct	55 ms	17488 KB	Output is correct
8	Correct	139 ms	22436 KB	Output is correct
9	Correct	137 ms	22628 KB	Output is correct
10	Correct	71 ms	17468 KB	Output is correct
11	Correct	151 ms	30120 KB	Output is correct
12	Correct	166 ms	29696 KB	Output is correct
13	Execution timed out	3520 ms	30248 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	17488 KB	Output is correct
2	Correct	95 ms	17520 KB	Output is correct
3	Correct	70 ms	17748 KB	Output is correct
4	Correct	496 ms	18004 KB	Output is correct
5	Correct	611 ms	18260 KB	Output is correct
6	Correct	68 ms	17544 KB	Output is correct
7	Correct	55 ms	17488 KB	Output is correct
8	Correct	139 ms	22436 KB	Output is correct
9	Correct	137 ms	22628 KB	Output is correct
10	Correct	71 ms	17468 KB	Output is correct
11	Correct	151 ms	30120 KB	Output is correct
12	Correct	166 ms	29696 KB	Output is correct
13	Execution timed out	3520 ms	30248 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Submission #863698

Compilation message