Submission #591161

#	Time	Username	Problem	Language	Result	Execution time	Memory
591161		GusterGoose27	Inside information (BOI21_servers)	C++11	55 / 100	257 ms	78024 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 rev_lca[MAXN][20];
bool flag = 0;
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);
		if (flag) {
			rev_lca[cur][0] = next;
		}
		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;
}

void move_u(int &i, int pow, int &s, int t) {
	pii r = lca_range[i][pow];
	if (s >= r.first || r.second >= t) return;
	s = r.second;
	i = lca[i][pow];
}

void move_d(int &i, int pow, int &s, int t) {
	int next = rev_lca[i][pow];
	pii r = lca_range_rev[next][pow];
	if (s >= r.first || r.second >= t) return;
	s = r.second;
	i = next;
}

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;
}

bool calc_lca(int a, int b, int e) {
	int s = -1;
	int diff = depth[a]-depth[b];
	int pow = 0;
	while (diff > 0) {
		if (diff & 1) {
			bool bo = move(a, pow, s);
			if (!bo) {
				return 0;
			}
		}
		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) {
				return 0;
			}
		}
		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) {
				return 0;
			}
			bo = move_rev(b, i, e);
			if (!bo) {
				return 0;
			}
		}
	}
	if (a != b) {
		bool bo = move(a, 0, s);
		if (!bo) {
			return 0;
		}
		bo = move_rev(b, 0, e);
		if (!bo) {
			return 0;
		}
	}
	if (s >= e) {
		return 0;
	}
	return 1;
}

int spec(int i) {
	int q = queries[i].first.first;
	int t = queries[i].first.second;
	int u = q;
	int d = q;
	int s1 = -1;
	int s2 = -1;
	for (int i = 19; i >= 0; i--) {
		move_u(u, i, s1, t);
		move_d(d, i, s2, t);
	}
	return (depth[d]-depth[u]+1);
}

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;
		a--;
		if (c == 'C') {
			queries[p++] = pair<pii, int>(pii(a, t), -1);
			flag = 1;
			continue;
		}
		cin >> b; b--;
		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);
	if (flag) rev_lca[n-1][0] = n-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);
			if (flag) rev_lca[j][i] = rev_lca[rev_lca[j][i-1]][i-1];
		}
	}
	for (int i = 0; i < k; i++) {
		if (queries[i].second == -1) {
			cout << spec(i) << "\n";
			continue;
		}
		bool b = calc_lca(queries[i].first.first, queries[i].first.second, queries[i].second);
		if (b) cout << "yes\n";
		else cout << "no\n";
	}
}

• 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: 5 / 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