Submission #1090724

#TimeUsernameProblemLanguageResultExecution timeMemory
1090724pokmui9909Inside information (BOI21_servers)C++17
0 / 100
21 ms18840 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define x first #define y second ll N, K; vector<pair<ll, ll>> T[120005]; ll S[120005], vis[120005], Ans[120005]; struct Query{ ll v, t, n; bool operator< (const Query &r) const{ return t < r.t; } }; vector<Query> Qry[120005]; struct Fen{ ll T[120005]; void upd(ll k, ll v) { while(k <= N) T[k] += v, k += k & -k; } ll qry(ll k) { ll r = 0; while(k >= 1) r += T[k], k -= k & -k; return r; } }seg; ll Size(ll u, ll p){ S[u] = 1; for(auto e : T[u]){ if(e.x != p && !vis[e.x]) S[u] += Size(e.x, u); } return S[u]; } ll Cent(ll u, ll p, ll n){ for(auto e : T[u]){ if(e.x != p && !vis[e.x] && S[e.x] > n / 2) return Cent(e.x, u, n); } return u; } ll Num[120005], X[120005], Y[120005], Z[120005]; void dfs(ll u, ll p, ll pc, vector<ll> &V, ll n){ V.push_back(u); Num[u] = n; for(auto e : T[u]){ if(e.x == p || vis[e.x]) continue; X[e.x] = -1, Y[e.x] = -1, Z[e.x] = min(Z[u], e.y); if(X[u] != -1 && pc > e.y) X[e.x] = X[u]; if(Y[u] != -1 && pc < e.y) Y[e.x] = e.y; dfs(e.x, u, e.y, V, n); } } void dnc(ll _u){ ll c = Cent(_u, -1, Size(_u, -1)); vis[c] = 1; vector<vector<ll>> Sub; Sub.push_back({c}); X[c] = 1, Y[c] = 0, Z[c] = N, Num[c] = c; for(auto e : T[c]){ if(vis[e.x]) continue; X[e.x] = Y[e.x] = Z[e.x] = e.y; Sub.push_back({}); dfs(e.x, -1, e.y, Sub.back(), e.x); } vector<Query> Q; vector<pair<ll, ll>> V, His; for(ll i = 0; i < Sub.size(); i++){ for(auto u : Sub[i]){ if(Y[u] != -1) V.push_back({Y[u], Z[u]}); for(auto q : Qry[u]){ if(q.v == -1){ Q.push_back({u, q.t, q.n}); } else if(Num[q.v] != 0 && Num[u] != Num[q.v] && Y[u] != -1 && Y[u] <= q.t && X[q.v] != -1 && Z[u] >= X[q.v]){ Ans[q.n] = -99; } } } } sort(Q.begin(), Q.end()); sort(V.begin(), V.end()); for(ll i = 0, j = 0; i < Q.size(); i++){ while(j < V.size() && V[j].x <= Q[i].t){ seg.upd(V[j].y, 1); His.push_back({V[j].y, 1}); j++; } if(X[Q[i].v] != -1) Ans[Q[i].n] += seg.qry(N) - seg.qry(X[Q[i].v] - 1); } for(auto t : His) seg.upd(t.x, -t.y); for(ll k = 0; k < Sub.size(); k++){ Q.clear(); V.clear(); His.clear(); for(auto u : Sub[k]){ if(Y[u] != -1) V.push_back({Y[u], Z[u]}); for(auto q : Qry[u]){ if(q.v == -1) Q.push_back({u, q.t, q.n}); } Num[u] = 0; } sort(Q.begin(), Q.end()); sort(V.begin(), V.end()); for(ll i = 0, j = 0; i < Q.size(); i++){ while(j < V.size() && V[j].x <= Q[i].t){ seg.upd(V[j].y, 1); His.push_back({V[j].y, 1}); j++; } if(X[Q[i].v] != -1) Ans[Q[i].n] -= seg.qry(N) - seg.qry(X[Q[i].v] - 1); } for(auto t : His) seg.upd(t.x, -t.y); } for(auto e : T[c]){ if(vis[e.x]) continue; dnc(e.x); } } int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> N >> K; ll t = 0; for(ll i = 1; i <= N + K - 1; i++){ char op; ll u, v; cin >> op >> u; if(op == 'S'){ cin >> v; t++; T[u].push_back({v, t}); T[v].push_back({u, t}); } else if(op == 'Q'){ cin >> v; if(u == v){ Ans[i - t] = -99; continue; } Qry[u].push_back({v, t, i - t}); Ans[i - t] = -100; } else { Qry[u].push_back({-1, t, i - t}); } } dnc(1); for(ll i = 1; i <= K; i++){ if(Ans[i] < 0){ cout << (Ans[i] == -100 ? "no\n" : "yes\n"); } else { cout << Ans[i] + 1 << '\n'; } } }

Compilation message (stderr)

servers.cpp: In function 'void dnc(ll)':
servers.cpp:65:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(ll i = 0; i < Sub.size(); i++){
      |                   ~~^~~~~~~~~~~~
servers.cpp:79:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 0, j = 0; i < Q.size(); i++){
      |                          ~~^~~~~~~~~~
servers.cpp:80:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         while(j < V.size() && V[j].x <= Q[i].t){
      |               ~~^~~~~~~~~~
servers.cpp:88:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(ll k = 0; k < Sub.size(); k++){
      |                   ~~^~~~~~~~~~~~
servers.cpp:99:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(ll i = 0, j = 0; i < Q.size(); i++){
      |                              ~~^~~~~~~~~~
servers.cpp:100:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             while(j < V.size() && V[j].x <= Q[i].t){
      |                   ~~^~~~~~~~~~
#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...