제출 #863512

#제출 시각아이디문제언어결과실행 시간메모리
863512Mizo_CompilerInside information (BOI21_servers)C++17
50 / 100
3598 ms33804 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; #define pb push_back #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define F first #define S second const int N = 120005; int n, pr[N], sz[N], q, dep[N], p[N][17], mn[N], vt[N]; int mx[N]; vector<array<int, 3>> qr; vector<pair<int, int>> adj[N]; int findp(int u) { return pr[u] = (pr[u] == u ? u : findp(pr[u])); } void merge(int u, int v) { u = findp(u), v = findp(v); if (u == v)return; if (sz[u] < sz[v])swap(u, v); sz[u] += sz[v]; pr[v] = u; } void init(int u, int par) { for (auto &[v, t] : adj[u]) { if (v == par)continue; p[v][0] = u; dep[v] = dep[u]+1; vt[v] = t; mn[v] = (vt[v] < vt[u] ? mn[u] : u); mx[v] = (vt[v] > vt[u] ? mx[u] : u); for (int i = 1; i < 17; i++) { p[v][i] = p[p[v][i-1]][i-1]; } init(v, u); } } int lift(int u, int k) { for (int i = 0; i < 17; i++) { if ((k & (1 << i)))u = p[u][i]; } return u; } int lca(int u, int v) { if (dep[u] < dep[v])swap(u, v); u = lift(u, dep[u]-dep[v]); if (u == v)return u; for (int i = 16; i >= 0; i--) { if (p[u][i] != p[v][i]) { u = p[u][i]; v = p[v][i]; } } return p[u][0]; } bool sol(int u, int v) { if (findp(u) != findp(v))return false; int l = lca(u, v); if (dep[mx[u]] > dep[l])return false; if (dep[mn[v]] > dep[l])return false; if (l == v || l == u)return true; u = lift(u, dep[u]-dep[l]-1); v = lift(v, dep[v]-dep[l]-1); return (vt[v] < vt[u]); } int main () { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 0; i < n; i++) { pr[i] = i, sz[i] = 1; } q += n-1; for (int i = 0; i < q; i++) { char c; cin >> c; if (c == 'S') { int u, v; cin >> u >> v; --u, --v; qr.pb({0, u, v}); adj[u].pb({v, i}); adj[v].pb({u, i}); } else if (c == 'Q') { int u, v; cin >> u >> v; --u, --v; qr.pb({1, u, v}); } else { int u; cin >> u; --u; qr.pb({2, u, u}); } } vt[0] = q+5; init(0, 0); for (auto &[op, u, v] : qr) { if (!op)merge(u, v); else if (op == 1) { cout << (sol(u, v) ? "yes\n" : "no\n"); } else { int cnt = 0; for (int i = 0; i < n; i++) { cnt += sol(i, u); } cout << cnt << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...