Submission #863702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
863702	2023-10-20T17:43:17 Z	TAhmed33	Inside information (BOI21_servers)	C++	15 / 100	3500 ms	30460 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 if (x == 'Q') {
			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	68 ms	17400 KB	Output is correct
2	Correct	94 ms	17496 KB	Output is correct
3	Correct	70 ms	17744 KB	Output is correct
4	Correct	434 ms	18048 KB	Output is correct
5	Correct	620 ms	18192 KB	Output is correct
6	Correct	70 ms	17732 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	17400 KB	Output is correct
2	Correct	94 ms	17496 KB	Output is correct
3	Correct	70 ms	17744 KB	Output is correct
4	Correct	434 ms	18048 KB	Output is correct
5	Correct	620 ms	18192 KB	Output is correct
6	Correct	70 ms	17732 KB	Output is correct
7	Incorrect	61 ms	17280 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	51 ms	17396 KB	Output is correct
2	Correct	143 ms	22392 KB	Output is correct
3	Correct	142 ms	22212 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	17396 KB	Output is correct
2	Correct	143 ms	22392 KB	Output is correct
3	Correct	142 ms	22212 KB	Output is correct
4	Incorrect	55 ms	17472 KB	Extra information in the output file
5	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	17392 KB	Output is correct
2	Correct	157 ms	29960 KB	Output is correct
3	Correct	164 ms	29752 KB	Output is correct
4	Execution timed out	3529 ms	29872 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	17392 KB	Output is correct
2	Correct	157 ms	29960 KB	Output is correct
3	Correct	164 ms	29752 KB	Output is correct
4	Execution timed out	3529 ms	29872 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	17488 KB	Output is correct
2	Correct	169 ms	22312 KB	Output is correct
3	Correct	171 ms	22844 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	17488 KB	Output is correct
2	Correct	169 ms	22312 KB	Output is correct
3	Correct	171 ms	22844 KB	Output is correct
4	Incorrect	61 ms	17488 KB	Extra information in the output file
5	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	17488 KB	Output is correct
2	Correct	159 ms	30116 KB	Output is correct
3	Correct	153 ms	29748 KB	Output is correct
4	Execution timed out	3510 ms	30192 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	17488 KB	Output is correct
2	Correct	159 ms	30116 KB	Output is correct
3	Correct	153 ms	29748 KB	Output is correct
4	Execution timed out	3510 ms	30192 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	17404 KB	Output is correct
2	Correct	94 ms	17468 KB	Output is correct
3	Correct	72 ms	17752 KB	Output is correct
4	Correct	449 ms	17744 KB	Output is correct
5	Correct	629 ms	17748 KB	Output is correct
6	Correct	66 ms	17744 KB	Output is correct
7	Correct	53 ms	17400 KB	Output is correct
8	Correct	131 ms	22392 KB	Output is correct
9	Correct	136 ms	22684 KB	Output is correct
10	Correct	71 ms	17392 KB	Output is correct
11	Correct	148 ms	30120 KB	Output is correct
12	Correct	165 ms	29728 KB	Output is correct
13	Execution timed out	3540 ms	30460 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	17404 KB	Output is correct
2	Correct	94 ms	17468 KB	Output is correct
3	Correct	72 ms	17752 KB	Output is correct
4	Correct	449 ms	17744 KB	Output is correct
5	Correct	629 ms	17748 KB	Output is correct
6	Correct	66 ms	17744 KB	Output is correct
7	Correct	53 ms	17400 KB	Output is correct
8	Correct	131 ms	22392 KB	Output is correct
9	Correct	136 ms	22684 KB	Output is correct
10	Correct	71 ms	17392 KB	Output is correct
11	Correct	148 ms	30120 KB	Output is correct
12	Correct	165 ms	29728 KB	Output is correct
13	Execution timed out	3540 ms	30460 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Submission #863702

Compilation message