Submission #1240615

#TimeUsernameProblemLanguageResultExecution timeMemory
1240615quannnguyen2009Inside information (BOI21_servers)C++20
0 / 100
20 ms14660 KiB
#include<bits/stdc++.h> #define int long long #define fi first #define se second #define pb push_back #define ii pair<int, int> #define sz(v) (int)v.size() #define all(v) v.begin(), v.end() using namespace std; const int N = 1.2e5+5, mod = 1e9+7, inf = 1e18; int n, q; vector<ii> adj[N]; vector<ii> q1[N]; vector<int> q2[N]; bool del[N], cur[N], inc[N], dcr[N]; int que[N], sz[N], wgt[N], ans[N]; int bit[2*N]; int get(int p) { p++; int idx = p, ans = 0; while (idx>0) { ans += bit[idx]; idx -= (idx&(-idx)); } return ans; } void upd(int u, int v) { u++; int idx = u; while (idx<2*N) { bit[idx]+=v; idx+=(idx&(-idx)); } } void dfs_sz(int u, int p) { sz[u] = 1; for (auto [v, w]: adj[u]) { if (v==p) continue; if (del[v]) continue; dfs_sz(v, u); sz[u] += sz[v]; } } int find_cen(int u, int p, int n) { for (auto [v, w]: adj[u]) { if (v==p) continue; if (del[v]) continue; if (sz[v]*2>n) return find_cen(v, u, n); } return u; } bool cmp(ii a, ii b) { return a.se>b.se; } void dfs_cal(int u, int p, int st) { inc[u] = inc[p]; if (!st && wgt[u]<wgt[p]) inc[u] = 0; dcr[u] = dcr[p]; if (!st && wgt[u]>wgt[p]) dcr[u] = 0; for (auto [it, id]: q1[u]) { if (cur[it] && inc[it] && dcr[u] && wgt[it]<=id) ans[id] = 1; } for (int it: q2[u]) { if (dcr[u]) ans[it] += get(it); } for (auto [v, w]: adj[u]) { if (v==p) continue; if (del[v]) continue; wgt[v] = w; if (st) dfs_cal(v, u, !st); else dfs_cal(v, u, st); } } void dfs_upd(int u, int p) { if (inc[u]) { upd(wgt[u], 1); cur[u] = 1; } for (auto [v, w]: adj[u]) { if (v==p) continue; if (del[v]) continue; dfs_upd(v, u); } } void dfs_clear(int u, int p) { if (inc[u]) { upd(wgt[u], -1); cur[u] = 0; } for (auto [v, w]: adj[u]) { if (v==p) continue; if (del[v]) continue; dfs_clear(v, u); } } void solve(int u) { dfs_sz(u, 0); u = find_cen(u, 0, sz[u]); del[u] = cur[u] = 1; inc[u] = dcr[u] = 1; wgt[u] = 0; upd(0, 1); sort(all(adj[u]), cmp); for (auto [v, w]: adj[u]) { if (del[v]) continue; wgt[v] = w; dfs_cal(v, u, 1); dfs_upd(v, u); } for (auto [it, id]: q1[u]) { if (cur[it] && inc[it] && wgt[it]<=id) ans[id] = 1; } for (int it: q2[u]) { ans[it] += get(it); } dfs_clear(u, 0); for (auto [v, w]: adj[u]) { if (del[v]) continue; solve(v); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for (int i=1; i<n+q; i++) { char typ; cin >> typ; if (typ=='S') { int u, v; cin >> u >> v; adj[u].pb({v, i}); adj[v].pb({u, i}); } else if (typ=='Q') { int x, y; cin >> x >> y; q1[y].pb({x, i}); que[i] = 1; } else { int x; cin >> x; q2[x].pb(i); que[i] = 2; } } solve(1); for (int i=1; i<n+q; i++) { if (que[i]==1) { if (ans[i]) cout << "yes\n"; else cout << "no\n"; } else if (que[i]==2) cout << ans[i] << '\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...