제출 #1082116

#제출 시각아이디문제언어결과실행 시간메모리
1082116VinhLuuInside information (BOI21_servers)C++17
5 / 100
118 ms47444 KiB
#include <bits/stdc++.h> //#define int long long #define ll long long #define fi first #define se second #define pb push_back #define all(lmao) lmao.begin(), lmao.end() using namespace std; typedef pair<int,int> pii; typedef tuple<int,int,int> tp; const int N = 2e5 + 5; const int oo = 2e9; struct IT { int st[N << 2], lz[N << 2]; void dolz(int i,int l,int r){ if(!lz[i]) return; int x = lz[i], mid = (l + r) / 2; lz[i] = 0; st[i << 1] += x * (mid - l + 1), st[i << 1|1] += x * (r - mid); lz[i << 1] += x, lz[i << 1|1] += x; } void update(int i,int l,int r,int u,int v,int x){ if(l > r || r < u || v < l) return; if(u <= l && r <= v){ st[i] += x * (r - l + 1); lz[i] += x; return; } dolz(i, l, r); int mid = (l + r) / 2; update(i << 1, l, mid, u, v, x); update(i << 1|1, mid + 1, r, u, v, x); st[i] = st[i << 1] + st[i << 1|1]; } int get(int i,int l,int r,int u,int v){ if(l > r || r < u || v < l) return 0; if(u <= l && r <= v) return st[i]; dolz(i, l, r); int mid = (l + r) / 2; return get(i << 1, l, mid, u, v) + get(i << 1|1, mid + 1, r, u, v); } } f[2]; struct DSU{ int par[N]; void re(int n){ for(int i = 1; i <= n; i ++) par[i] = i; } int fin(int u){ return par[u] == u ? u : par[u] = fin(par[u]); } void dsu(int u,int v){ u = fin(u); v = fin(v); if(u == v) return; par[u] = v; } } g[2]; int n, q, T[N], X[N], Y[N], in[N], demin, en[N], head[N], pa[N], dp[N][22], d[N], be[N], h[N], key[2][N], tn[N]; vector<pii> p[N]; bool kt(int u,int v){ return in[u] <= in[v] && in[v] <= en[u]; } int LCA(int u,int v){ if(kt(u, v)) return u; int lca = u; for(int i = 20; i >= 0; i --) if(kt(dp[u][i], v)) lca = dp[u][i]; else u = dp[u][i]; return lca; } void dfs(int u,int v){ d[u] = 1; for(auto [j, w] : p[u]) if(j != v){ dfs(j, u); d[u] += d[j]; pa[j] = u; h[j] = w; } } int scc = 1; vector<int> vr[N], b[N]; void hld(int u,int v){ in[u] = ++demin; if(!head[scc]) head[scc] = u; be[u] = scc; tn[demin] = u; if(!v){ for(int i = 0; i <= 20; i ++) dp[u][i] = u; }else{ dp[u][0] = v; for(int i = 1; i <= 20; i ++) dp[u][i] = dp[dp[u][i - 1]][i - 1]; } int mx = 0, val = 0; for(auto [j, w] : p[u]) if(j != v && d[j] > d[mx]) val = w, mx = j; key[0][u] = mx, key[1][u] = val; if(mx) hld(mx, u); for(auto [j, w] : p[u]) if(j != v && j != mx){ scc++; vr[u].pb(w); hld(j, u); } sort(all(vr[u])); for(auto j : vr[u]) b[u].pb(0); en[u] = demin; } void up(int u,int tmp){ if(h[pa[u]] <= tmp){ if(pa[u] == 1){ g[0].dsu(u, pa[u]); g[1].dsu(u, pa[u]); }else{ if(h[pa[u]] > h[u]) g[0].dsu(u, pa[u]); else g[1].dsu(u, pa[u]); } } for(auto [j, w] : p[u]) if(j != pa[u]){ if(w > h[u] && w <= tmp) g[1].dsu(j, u); if(w < h[u] && w <= tmp) g[0].dsu(j, u); } int v = g[1].fin(u), val = f[0].get(1, 1, n, in[u], in[u]); if(v != 1 && key[1][pa[v]] != h[v]){ if(key[1][pa[v]] < h[v]) f[1].update(1, 1, n, in[pa[v]], in[pa[v]], val); int dr = lower_bound(all(vr[pa[v]]), h[v]) - vr[pa[v]].begin(); b[pa[v]][dr] += val; // add } if(u == v) return; if(key[0][pa[u]] != u){ int dr = lower_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin(); b[pa[u]][dr] += val; // add if(key[1][pa[u]] < h[u]) f[1].update(1, 1, n, in[pa[u]], in[pa[u]], val); } u = pa[u]; while(true){ if(be[u] == be[v]){ f[0].update(1, 1, n, in[v], in[u], val); return; } int j = pa[head[be[u]]]; if(h[head[be[u]]] > key[1][tn[in[j]]]) f[1].update(1, 1, n, in[j], in[j], val); int dr = lower_bound(all(vr[j]), h[head[be[u]]]) - vr[j].begin(); b[j][dr] += val; // add f[0].update(1, 1, n, in[head[be[u]]], in[u], val); u = j; } } int lc(int u,int v){ int kq = u; if(u == v) return kq; for(int i = 20; i >= 0; i --) if(v != dp[u][i] && kt(v, dp[u][i])){ kq = dp[u][i]; u = dp[u][i]; } return kq; } int query(int u,int v,int tmp){ int lca = LCA(u, v); int fu = g[0].fin(u), fv = g[1].fin(v); if(h[fu] <= tmp) fu = pa[fu]; if(h[fv] <= tmp) fv = pa[fv]; if(kt(fu, lca) && kt(fv, lca)){ fu = lc(u, lca), fv = lc(v, lca); if(fu == lca || fv == lca || h[fu] < h[fv]) return 1; } return 0; } int solve(int u,int tmp){ int ans = 1; for(int i = 0; i < vr[u].size(); i ++) ans += b[u][i]; if(h[key[0][u]] <= tmp && key[0][u]) ans += f[0].get(1, 1, n, in[key[0][u]], in[key[0][u]]); if(u == 1) return ans; int v = g[0].fin(u); if(h[v] <= tmp) v = pa[v]; if(u == v) return ans; if(key[0][pa[u]] != u){ int dr = upper_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin(); for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i]; ans++; if(h[key[0][pa[u]]] <= tmp && key[1][pa[u]] > h[u]) ans += f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]); }else{ ans += f[1].get(1, 1, n, in[pa[u]], in[pa[u]]); } u = pa[u]; while(true){ if(be[u] == be[v]){ if(u == v) return ans; ans += f[1].get(1, 1, n, in[v], in[u] - 1); return ans; } int j = pa[head[be[u]]]; // cerr << j << " t\n"; int k = head[be[u]]; int pos = upper_bound(all(vr[j]), h[k]) - vr[j].begin(); for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i]; ans += f[1].get(1, 1, n, in[k], in[u] - 1); ans++; if(h[key[0][j]] <= tmp && key[1][j] > h[k]) ans += f[0].get(1, 1, n, in[key[0][j]], in[key[0][j]]); u = j; } return ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "v" if(fopen(task ".inp","r")){ freopen(task ".inp","r",stdin); freopen(task ".out","w",stdout); } cin >> n >> q; q = n + q - 1; g[1].re(n), g[0].re(n); for(int i = 1; i <= q; i ++){ char c; cin >> c; if(c == 'S'){ cin >> X[i] >> Y[i]; T[i] = 0, p[X[i]].pb({Y[i], i}); p[Y[i]].pb({X[i], i}); }else if(c == 'Q'){ T[i] = 1; cin >> X[i] >> Y[i]; }else{ T[i] = 2; cin >> X[i]; } } pa[1] = 1; h[1] = 0; dfs(1, 0); hld(1, 0); for(int i = 1; i <= n; i ++) f[0].update(1, 1, n, in[i], in[i], 1), f[1].update(1, 1, n, in[i], in[i], 1); for(int i = 1; i <= q; i ++){ if(T[i] == 0){ if(in[X[i]] < in[Y[i]]) swap(X[i], Y[i]); up(X[i], i); }else if(T[i] == 1){ int x = X[i], y = Y[i]; if(in[x] > in[y]) swap(x, y); if(pa[y] == x){ if(h[y] <= i) cout << "yes\n"; else cout << "no\n"; continue; } cout << (query(Y[i], X[i], i) == 1 ? "yes\n" : "no\n"); }else { cout << solve(X[i], i) << "\n"; } } }

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void hld(int, int)':
servers.cpp:121:12: warning: unused variable 'j' [-Wunused-variable]
  121 |   for(auto j : vr[u]) b[u].pb(0);
      |            ^
servers.cpp: In function 'int solve(int, int)':
servers.cpp:192:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |   for(int i = 0; i < vr[u].size(); i ++) ans += b[u][i];
      |                  ~~^~~~~~~~~~~~~~
servers.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
      |                     ~~^~~~~~~~~~~~~~~~~~
servers.cpp:218:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
      |                      ~~^~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:231:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:232:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...