제출 #541818

#제출 시각아이디문제언어결과실행 시간메모리
541818StickfishInside information (BOI21_servers)C++17
100 / 100
624 ms47880 KiB
#include <iostream> #include <algorithm> #include <bitset> #include <vector> using namespace std; struct way { int mnt = -177013; int mxt = -177013; bool incr = true; bool dcr = true; way() {} way(int t): mnt(t), mxt(t) {} way reverse() { way ans; ans.mnt = mnt; ans.mxt = mxt; ans.dcr = incr; ans.incr = dcr; return ans; } way operator+(way w) { if (mnt == -177013) return w; if (w.mnt == -177013) return *this; way ans; ans.mnt = min(mnt, w.mnt); ans.mxt = max(mxt, w.mxt); ans.incr = (incr && w.incr && mxt <= w.mnt); ans.dcr = (dcr && w.dcr && mnt >= w.mxt); return ans; } friend ostream& operator<<(ostream& o, way w) { o << "[" << w.incr << ' ' << w.dcr << ' ' << w.mnt << ' ' << w.mxt << "]"; return o; } }; const int MAXN = 120008; vector<pair<int, int>> edg[MAXN]; int depth[MAXN]; pair<int, int> rt[MAXN]; pair<int, way> crt[MAXN]; void dfs(int v) { auto [rtv, tmv] = rt[v]; int par = crt[rtv].first; int parpar = crt[par].first; if (depth[rtv] - depth[par] == depth[par] - depth[parpar]) { crt[v] = {parpar, way(tmv) + crt[rtv].second + crt[par].second}; } else { crt[v] = {rtv, way(tmv)}; } for (auto [u, t] : edg[v]) { if (u == rtv) continue; rt[u] = {v, t}; depth[u] = depth[v] + 1; dfs(u); } } pair<int, way> lift(int v, int d) { way ans = rt[v].second; while (d) { if (depth[v] - depth[crt[v].first] <= d) { ans = ans + crt[v].second; d -= depth[v] - depth[crt[v].first]; v = crt[v].first; } else { ans = ans + rt[v].second; --d; v = rt[v].first; } } return {v, ans}; } pair<int, pair<way, way>> lca(int v, int u) { way ansv = -177013; way ansu = -177013; if (depth[v] > depth[u]) { pair<int, way> vlift = lift(v, depth[v] - depth[u]); ansv = ansv + vlift.second; v = vlift.first; } else if (depth[v] < depth[u]) { pair<int, way> ulift = lift(u, depth[u] - depth[v]); ansu = ansu + ulift.second; u = ulift.first; } while (u != v) { if (crt[v].first != crt[u].first) { ansv = ansv + crt[v].second; ansu = ansu + crt[u].second; v = crt[v].first; u = crt[u].first; } else { ansv = ansv + rt[v].second; ansu = ansu + rt[u].second; v = rt[v].first; u = rt[u].first; } } return {v, {ansv, ansu}}; } way get_way(int v, int u) { auto ans = lca(v, u); return ans.second.first + ans.second.second.reverse(); } int centrt[MAXN]; int sz[MAXN]; bitset<MAXN> used; vector<pair<int, int>> ways[MAXN]; void sz_dfs(int v, int rtv) { sz[v] = 1; for (auto [u, t] : edg[v]) { if (u == rtv || used[u]) continue; sz_dfs(u, v); sz[v] += sz[u]; } } int centr_dfs(int v, int sz0) { for (auto [u, t] : edg[v]) { if (sz[u] > sz[v] || used[u]) continue; if (sz[u] * 2 > sz0) return centr_dfs(u, sz0); } return v; } void centrinit_dfs(int v, int rtv, int grt, way w, vector<pair<int, int>>& remilia) { if (w.incr) remilia.push_back({w.mnt, w.mxt}); centrt[v] = grt; for (auto [u, t] : edg[v]) { if (used[u] || u == rtv) continue; centrinit_dfs(u, v, grt, w + t, remilia); } } void centr_decompose(int v) { sz_dfs(v, -1); v = centr_dfs(v, sz[v]); //cout << v << endl; used[v] = 1; for (auto [u, t] : edg[v]) { if (used[u]) continue; centrinit_dfs(u, v, v, t, ways[v]); centr_decompose(u); } } vector<pair<pair<int, int>, int>> subqr[MAXN]; int ans_qr2(int v, int qrnum, int mxt) { int ans = 0; int u = v; while (u > -1) { //cout << "(" << u << ' ' << v << ") "; way w = get_way(v, u); if (w.incr && w.mxt <= mxt) { //cout << u << ' ' << v << ": "; //cout << "{" << w.mnt << ' ' << w.mxt << "} "; ++ans; subqr[u].push_back({{w.mxt + 1, mxt}, qrnum}); //for (auto [mnt0, mxt0] : ways[u]) { //if (mnt0 > w.mxt && mxt0 <= mxt) { //cout << "(" << mnt0 << ' ' << mxt0 << ") "; //++ans; //} else { //cout << "[" << mnt0 << ' ' << mxt0 << "] "; //} //} //cout << endl; } u = centrt[u]; } return ans; } struct fenwick { void resize(int n) { t.resize(n); } void add(int i, int x) { while (i < t.size()) { t[i] += x; i |= i + 1; } } int get(int i) { int ans = 0; while (i >= 0) { ans += t[i]; i &= i + 1; --i; } return ans; } private: vector<int> t; }; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k; cin >> n >> k; vector<pair<int, pair<int, int>>> qrs; int timer = -1; for (int i = 0; i < n + k - 1; ++i) { char ch; cin >> ch; if (ch == 'S') { int u, v; cin >> u >> v; --u, --v; edg[u].push_back({v, ++timer}); edg[v].push_back({u, timer}); } else if (ch == 'Q') { int u, v; cin >> u >> v; --u, --v; qrs.push_back({timer, {v, u}}); } else { int v; cin >> v; --v; qrs.push_back({timer, {v, -1}}); } } rt[0] = {0, -177013}; dfs(0); for (int i = 0; i < n; ++i) centrt[i] = -1; centr_decompose(0); vector<int> anss(k); for (int i = 0; i < k; ++i) { auto [t, qri] = qrs[i]; auto [v, u] = qri; if (u == -1) { anss[i] = ans_qr2(v, i, t); } else { way w = get_way(v, u); if (w.incr && w.mxt <= t) { anss[i] = -1; } else { anss[i] = -2; } } } fenwick tr; tr.resize(n); for (int v = 0; v < n; ++v) { sort(subqr[v].rbegin(), subqr[v].rend()); sort(ways[v].begin(), ways[v].end()); int j = ways[v].size(); for (auto [hey, qi] : subqr[v]) { auto [l, r] = hey; while (j > 0 && ways[v][j - 1].first >= l) { --j; tr.add(ways[v][j].second, 1); } anss[qi] += tr.get(r); //for (auto [l0, r0] : ways[v]) { //if (l <= l0 && r0 <= r) { //++anss[qi]; //} //} } while (j < ways[v].size()) { tr.add(ways[v][j].second, -1); ++j; } } for (int i = 0; i < k; ++i) { if (anss[i] == -1) cout << "yes\n"; else if (anss[i] == -2) cout << "no\n"; else cout << anss[i] << '\n'; } }

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

servers.cpp: In member function 'void fenwick::add(int, int)':
servers.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         while (i < t.size()) {
      |                ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:288:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |         while (j < ways[v].size()) {
      |                ~~^~~~~~~~~~~~~~~~
#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...