Submission #591148

#	Time	Username	Problem	Language	Result	Execution time	Memory
591148		GusterGoose27	Inside information (BOI21_servers)	C++11	50 / 100	248 ms	67080 KiB

servers

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 120000;
vector<pii> edges[MAXN];
pair<pii, int> queries[MAXN]; // start, end, time
int lca[MAXN][20];
pii lca_range[MAXN][20];
pii lca_range_rev[MAXN][20];
int depth[MAXN];
int n, k;

void dfs(int cur = 0, int p = -1) {
	for (pii e: edges[cur]) {
		int next = e.first;
		if (next == p) continue;
		depth[next] = depth[cur]+1;
		lca[next][0] = cur;
		lca_range[next][0] = pii(e.second, e.second);
		lca_range_rev[next][0] = pii(e.second, e.second);
		dfs(next, cur);
	}
}

bool move(int &i, int pow, int &s) {
	pii r = lca_range[i][pow];
	if (s >= r.first) return 0;
	s = r.second;
	i = lca[i][pow];
	return 1;
}

bool move_rev(int &i, int pow, int &e) {
	pii r = lca_range_rev[i][pow];
	if (r.second >= e || r.second == -1) return 0;
	e = r.first;
	i = lca[i][pow];
	return 1;
}

void calc_lca(int i) {
	int a = queries[i].first.first;
	int b = queries[i].first.second;
	int s = -1;
	int e = queries[i].second;
	int diff = depth[a]-depth[b];
	int pow = 0;
	while (diff > 0) {
		if (diff & 1) {
			bool bo = move(a, pow, s);
			if (!bo) {
				cout << "no\n";
				return;
			}
		}
		pow++;
		diff /= 2;
	}
	diff = depth[b]-depth[a];
	pow = 0;
	while (diff > 0) {
		if (diff & 1) {
			bool bo = move_rev(b, pow, e);
			if (!bo) {
				cout << "no\n";
				return;
			}
		}
		pow++;
		diff /= 2;
	}
	for (int i = 19; i >= 0; i--) {
		if (lca[a][i] != lca[b][i]) {
			bool bo = move(a, i, s);
			if (!bo) {
				cout << "no\n";
				return;
			}
			bo = move_rev(b, i, e);
			if (!bo) {
				cout << "no\n";
				return;
			}
		}
	}
	if (a != b) {
		bool bo = move(a, 0, s);
		if (!bo) {
			cout << "no\n";
			return;
		}
		bo = move_rev(b, 0, e);
		if (!bo) {
			cout << "no\n";
			return;
		}
	}
	if (s >= e) {
		cout << "no\n";
	}
	else cout << "yes\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k;
	int t = 0;
	int p = 0;
	for (int i = 0; i < n+k-1; i++) {
		char c;
		int a, b;
		cin >> c >> a >> b;
		a--; b--;
		assert(c != 'C');
		if (c == 'S') {
			edges[a].push_back(pii(b, t));
			edges[b].push_back(pii(a, t));
			t++;
		}
		else {
			queries[p] = pair<pii, int>(pii(b, a), t);
			p++;
		}
	}
	assert(t == n-1);
	assert(p == k);
	dfs();
	lca_range[0][0] = pii(-1, -1);
	lca_range_rev[0][0] = pii(-1, -1);
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			lca[j][i] = lca[lca[j][i-1]][i-1];
			pii r1 = lca_range[j][i-1];
			pii r2 = lca_range[lca[j][i-1]][i-1];
			if (r1.second >= 0 && r1.second < r2.first) lca_range[j][i] = pii(r1.first, r2.second);
			else lca_range[j][i] = pii(-1, -1);
			r1 = lca_range_rev[j][i-1];
			r2 = lca_range_rev[lca[j][i-1]][i-1];
			if (r2.second >= 0 && r2.second < r1.first) lca_range_rev[j][i] = pii(r2.first, r1.second);
			else lca_range_rev[j][i] = pii(-1, -1);
		}
	}
	for (int i = 0; i < k; i++) {
		calc_lca(i);
	}
}

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