Submission #1183958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183958		tamyte	Inside information (BOI21_servers)	C++20	48 / 100	171 ms	55496 KiB

servers

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;
struct info {
	int a, t;
};
struct DSU {
	vector<int> e;
	DSU(int n) {
		e = vector<int>(n, -1);
	}
	int get(int x) {
		return e[x] < 0 ? x : e[x] = get(e[x]);
	}
	void unite(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
	}
} dsu(MAXN);
int increas[MAXN + 1];
int decreas[MAXN + 1];
int w[MAXN + 1];
vector<info> adj[MAXN + 1];
int d[MAXN + 1];
int lift[MAXN + 1][20];

void dfs(int v, int p) {
	for (auto& [a, t] : adj[v]) {
		if (a == p) continue;
		w[a] = t;
		increas[a] = decreas[a] = v;
		if (w[a] > w[v]) increas[a] = increas[v];
		else decreas[a] = decreas[v];
		d[a] = d[v] + 1;
		int curr = lift[a][0] = v;
		for (int x = 0; x < 20; ++x) {
			if (curr == -1) continue;
			curr = lift[a][x + 1] = lift[curr][x]; 
		}
		dfs(a, v);
	}
}
int move(int i, int j) {
	for (int k = 0; k < 20; ++k) {
		if (j >> k & 1) {
			i = lift[i][k];
		}
	}
	return i;
}
int lca(int i, int j) {
	if (d[i] < d[j]) swap(i, j);
	i = move(i, d[i] - d[j]);
	if (i == j) return i;
	for (int x = 19; x >= 0; --x) {
		if (lift[i][x] != lift[j][x]) {
			i = lift[i][x];
			j = lift[j][x];
		}
	}
	return lift[i][0];
}
bool has_data(int a, int b) {
	int x = lca(a, b);
	if (x == a) {
		if (d[decreas[b]] <= d[x]) {
			return true;
		}
		return false;
	} else if (x == b) {
		if (d[increas[a]] <= d[x]) {
			return true;
		}
		return false;
	}
	bool ok = true;
	if (d[decreas[b]] > d[x]) ok = false;
	if (d[increas[a]] > d[x]) ok = false;
	a = move(a, d[a] - d[x] - 1);
	b = move(b, d[b] - d[x] - 1);
	if (w[a] < w[b]) ok = false;
	return ok;
}

int main() {
	int n, k;
	cin >> n >> k;
	int in = 0;
	vector<tuple<char, int, int>> queries;
	for (int i = 0; i < n + k - 1; ++i) {
		char c;
		cin >> c;
		if (c == 'S') {
			int a, b;
			cin >> a >> b;
			--a; --b;
			info i1;
			i1.a = b;
			i1.t = in;
			adj[a].push_back(i1);
			i1.a = a;
			adj[b].push_back(i1);
			queries.push_back({c, a, b});
			in++;			
		} else if (c == 'Q') {
			int a, b;
			cin >> a >> b;
			--a; --b;
			queries.push_back({c, a, b});
		}
	}
	increas[0] = decreas[0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 20; ++j) {
			lift[i][j] = -1;
		}
	}
	dfs(0, -1);
	// for (int i = 0; i < n; ++i) {
		// cout << increas[i] << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < n; ++i) {
		// cout << decreas[i] << " ";
	// }
	// cout << endl;
	for (auto [a, b, c] : queries) {
		if (a == 'S') {
			dsu.unite(b, c);
		} else {
			if (dsu.get(b) == dsu.get(c) &&
				has_data(b, c)) {
				cout << "yes\n";
			} else {
				cout << "no\n";
			}
 		}
	}
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 0 / 18