Submission #534367

#	Time	Username	Problem	Language	Result	Execution time	Memory
534367		skittles1412	Inside information (BOI21_servers)	C++17	57 / 100	245 ms	56988 KiB

servers

#include "bits/extc++.h"
 
using namespace std;
 
template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}
 
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}
 
#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif
 
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
 
using Q = const vector<tuple<char, int, int>>&;
 
void yno(bool b) {
	if (b) {
		cout << "yes" << endl;
	} else {
		cout << "no" << endl;
	}
}
 
namespace s1 {
 
bool solve(int n, Q queries) {
	if (n > 4000) {
		return false;
	}
	vector<int> arr[n];
	for (int i = 0; i < n; i++) {
		arr[i] = {i};
	}
	int cnt[n] {};
	for (auto& [c, u, v] : queries) {
		if (c == 'S') {
			if (sz(arr[v]) > sz(arr[u])) {
				swap(arr[u], arr[v]);
			}
			vector<int> out(sz(arr[u]) + sz(arr[v]));
			merge(begin(arr[u]), end(arr[u]), begin(arr[v]), end(arr[v]), out.begin());
			arr[u] = out;
			swap(out, arr[v]);
			for (auto& a : arr[u]) {
				cnt[a]++;
			}
		} else if (c == 'Q') {
			if (binary_search(begin(arr[u]), end(arr[u]), v)) {
				cout << "yes" << endl;
			} else {
				cout << "no" << endl;
			}
		} else {
			cout << cnt[u] + 1 << endl;
		}
	}
	return true;
}
 
}  // namespace s1
 
namespace s2 {
 
bool solve(int n, Q queries) {
	for (auto& [c, u, v] : queries) {
		if (c == 'S' && u && v) {
			return false;
		}
	}
	vector<int> vals;
	int ord[n], oind = 0;
	memset(ord, -1, sizeof(ord));
	for (auto& [c, u, v] : queries) {
		if (c == 'S') {
			int x = u;
			if (!x) {
				x = v;
			}
			vals.push_back(x);
			ord[x] = oind++;
		} else if (c == 'Q') {
			if (u == v) {
				yno(true);
			} else if (u == 0) {
				yno(ord[v] != -1);
			} else if (v == 0) {
				yno(ord[u] != -1);
			} else {
				yno(ord[u] != -1 && ord[v] != -1 && ord[u] > ord[v]);
			}
		} else {
			if (u == 0) {
				cout << oind + 1 << endl;
			} else if (ord[u] == -1) {
				cout << 1 << endl;
			} else {
				cout << oind - ord[u] + 1 << endl;
			}
		}
	}
	return true;
}
 
}  // namespace s2
 
namespace s3 {
 
const int maxn = 2e5, logn = 20;
 
vector<pair<int, int>> graph[maxn];
int t, tin[maxn], tout[maxn], par[maxn], parv[maxn], lift1[logn][maxn], lift2[logn][maxn],
	liftv1[logn][maxn], liftv2[logn][maxn];
 
void dfs(int u, int p = -1) {
	tin[u] = t++;
	par[u] = lift1[0][u] = lift2[0][u] = p;
	for (auto& [v, w] : graph[u]) {
		if (v != p) {
			parv[v] = liftv1[0][v] = liftv2[0][v] = w;
			dfs(v, u);
		}
	}
	tout[u] = t++;
}
 
bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}
 
template <typename T>
int blift(int u, int v, int lift[logn][maxn], int liftv[logn][maxn], const T& t) {
	if (anc(u, v)) {
		return u;
	}
	int prev = -1;
	for (int i = logn - 1; i >= 0; i--) {
		int p = lift[i][u];
		if (p != -1 && !anc(p, v)) {
			if (prev != -1 && !t(prev, parv[u])) {
				return -1;
			}
			prev = liftv[i][u];
			u = p;
		}
	}
	if (lift[0][u] == -1) {
		return -1;
	}
	if (prev != -1 && !t(prev, parv[u])) {
		return -1;
	}
	return u;
}
 
bool solve(int n, Q queries) {
	for (auto& [c, _u, _v] : queries) {
		if (c == 'C') {
			return false;
		}
	}
	int ct = 0;
	for (auto& [c, u, v] : queries) {
		if (c == 'S') {
			graph[u].emplace_back(v, ct);
			graph[v].emplace_back(u, ct);
			ct++;
		}
	}
	dfs(0);
	// 1 - increasing upwards
	// 2 - decreasing upwards
	for (int i = 1; i < logn; i++) {
		for (int j = 0; j < n; j++) {
			{
				int p = lift1[i - 1][j];
				if (p != -1 && liftv1[i - 1][j] < parv[p]) {
					lift1[i][j] = lift1[i - 1][p];
					liftv1[i][j] = liftv1[i - 1][p];
				} else {
					lift1[i][j] = -1;
				}
			}
			{
				int p = lift2[i - 1][j];
				if (p != -1 && liftv2[i - 1][j] > parv[p]) {
					lift2[i][j] = lift2[i - 1][p];
					liftv2[i][j] = liftv2[i - 1][p];
				} else {
					lift2[i][j] = -1;
				}
			}
		}
	}
	ct = -1;
	for (auto [c, u, v] : queries) {
		if (c == 'S') {
			ct++;
		} else {
			swap(u, v);
			if (u == v) {
				yno(true);
			} else {
				int cu = blift(u, v, lift1, liftv1, [&](int a, int b) -> bool {
					return a < b;
				});
				int cv = blift(v, u, lift2, liftv2, [&](int a, int b) -> bool {
					return b < a;
				});
				if (cu != -1 && cv != -1) {
					dbg(u, v, cu, cv, par[cu], par[cv]);
					int lca = anc(u, v) ? u : par[cu];
					dbg(lca);
					if (lca != (anc(v, u) ? v : par[cv])) {
						yno(false);
						continue;
					}
					assert(lca == (anc(v, u) ? v : par[cv]));
					if (anc(u, v)) {
						yno(parv[v] <= ct);
					} else if (anc(v, u)) {
						yno(parv[cu] <= ct);
					} else {
						yno(parv[cu] < parv[cv] && parv[v] <= ct);
					}
				} else {
					yno(false);
				}
			}
		}
	}
	return true;
}
 
}  // namespace s3
 
void solve() {
	int n, q;
	cin >> n >> q;
	vector<tuple<char, int, int>> queries(n + q - 1);
	for (auto& [c, u, v] : queries) {
		cin >> c;
		if (c != 'C') {
			cin >> u >> v;
			u--;
			v--;
		} else {
			cin >> u;
			u--;
		}
	}
	s3::solve(n, queries) || s2::solve(n, queries) || s1::solve(n, queries);
}
 
int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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