Submission #863692

#	Time	Username	Problem	Language	Result	Execution time	Memory
863692		TAhmed33	Inside information (BOI21_servers)	C++98	0 / 100	89 ms	58896 KiB

servers

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120005;
const int MM = 15;
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[MM][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[0][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);
		assert(x >= 1 && x <= n);
		int a = queries[i].first, b = queries[i].second;
		swap(a, b);
		vector <int> d;
		while (a != x) {
			d.push_back(u[0][a]);
			a = dp[0][a];
			assert(a);
		}
		vector <int> g;
		while (b != x) {
			g.push_back(u[0][b]);
			b = dp[0][b];
			assert(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];
		flag &= (d.back() <= t[i]);
		cout << (flag ? "yes\n" : "no\n");
	}
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5