Submission #679454

#TimeUsernameProblemLanguageResultExecution timeMemory
679454qwerasdfzxclCollapse (JOI18_collapse)C++17
5 / 100
5785 ms49488 KiB
#include "collapse.h" #include <bits/stdc++.h> typedef long long ll; using namespace std; constexpr int B = 5050; struct DSU{ int path[100100], sz[100100], cnt; vector<pair<int, int>> mylog; void init(int n){for (int i=1;i<=n;i++){path[i] = i; sz[i] = 1;} mylog.clear(); cnt = 0;} int find(int s){ if (s==path[s]) return s; return find(path[s]); } bool merge(int x, int y){ //printf("merge: %d %d\n", x, y); x = find(x), y = find(y); if (x==y) return 0; cnt++; if (sz[x] > sz[y]) swap(x, y); path[x] = y; sz[y] += sz[x]; mylog.emplace_back(x, sz[x]); return 1; } void rollback(int c){ while(c--){ auto [x, _sz] = mylog.back(); mylog.pop_back(); sz[path[x]] -= _sz; path[x] = x; --cnt; } } int count(int x){return x - cnt;} }dsu; struct Edge{ int x, y; Edge(){} Edge(int _x, int _y): x(_x), y(_y) {} }E[100100]; struct Query{ int w, p, i; Query(){} Query(int _w, int _p, int _i): w(_w), p(_p), i(_i) {} }; vector<Query> bucket[100100]; map<int, int> mp[100100]; int idx[100100], updated[100100], on[100100], ans[100100]; bool cmpB(const Query &x, const Query &y){return x.p < y.p;} bool cmpE(int x, int y){return E[x].y < E[y].y;} void calc(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){ int c = T.size(), q = W.size(); ///init for (int i=1;i<=c;i++){ mp[i].clear(); on[i] = 0; updated[i] = 0; } for (int i=0;i<=c/B;i++) bucket[i].clear(); fill(E, E+c+1, Edge(0, 0)); /// int Ecnt = 0; for (int i=1;i<=c;i++){ int op, x, y; op = T[i-1], x = X[i-1], y = Y[i-1]; if (x==y) {idx[i] = 0; continue;} if (x > y) swap(x, y); if (mp[x].find(y)==mp[x].end()){ mp[x][y] = ++Ecnt; E[Ecnt] = Edge(x, y); } idx[i] = mp[x][y]; } for (int i=1;i<=q;i++){ int w, p; w = W[i-1], p = P[i-1]; bucket[w/B].emplace_back(w, p, i); } vector<int> onE; for (int z=0;z<=c/B;z++){ int l = z*B, r = (z+1)*B; for (int i=l;i<r;i++) if (idx[i]) updated[idx[i]] = 1; sort(bucket[z].begin(), bucket[z].end(), cmpB); dsu.init(n); int pt = 0; for (auto &[w, p, qi]:bucket[z]){ while(pt < (int)onE.size() && E[onE[pt]].y <= p){ if (!updated[onE[pt]]) dsu.merge(E[onE[pt]].x, E[onE[pt]].y); pt++; } for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1; int cnt = 0; for (int i=l;i<r;i++) if (idx[i] && on[idx[i]] && E[idx[i]].y <= p){ if (dsu.merge(E[idx[i]].x, E[idx[i]].y)) cnt++; } //printf("ok %d -> %d\n", qi, dsu.count(p)); ans[qi] += dsu.count(p); dsu.rollback(cnt); for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1; } for (int i=l;i<r;i++) if (idx[i]) on[idx[i]] ^= 1, updated[idx[i]] = 0; vector<int> nE; for (auto &x:onE) if (on[x]) nE.push_back(x); for (int i=l;i<r;i++) if (on[idx[i]]) nE.push_back(idx[i]); sort(nE.begin(), nE.end(), cmpE); nE.erase(unique(nE.begin(), nE.end()), nE.end()); swap(nE, onE); } } std::vector<int> simulateCollapse( int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y, std::vector<int> W, std::vector<int> P ) { for (auto &x:X) ++x; for (auto &x:Y) ++x; for (auto &x:W) ++x; for (auto &x:P) ++x; calc(N, T, X, Y, W, P); for (auto &x:X) x = N+1 - x; for (auto &y:Y) y = N+1 - y; for (auto &p:P) p = N - p; calc(N, T, X, Y, W, P); vector<int> ret(W.size()); for (int i=0;i<(int)W.size();i++) ret[i] = ans[i+1]; return ret; }

Compilation message (stderr)

collapse.cpp: In function 'void calc(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:72:13: warning: variable 'op' set but not used [-Wunused-but-set-variable]
   72 |         int op, x, y;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...