Submission #1261794

#TimeUsernameProblemLanguageResultExecution timeMemory
1261794icebearCollapse (JOI18_collapse)C++20
0 / 100
117 ms17600 KiB
// ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebear" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 1e5 + 5; const int S = 350; int n, q, c; struct DSU { vector<int> lab; vector<array<int, 4>> history; int connected; DSU(int n = 0): lab(n, -1), connected(0) {} int root(int v) { return (lab[v] < 0 ? v : lab[v] = root(lab[v])); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (lab[u] > lab[v]) swap(u, v); history.pb({u, v, lab[u], lab[v]}); connected++; lab[u] += lab[v]; lab[v] = u; return true; } void roll_back() { while(!history.empty()) { auto tmp = history.back(); history.pop_back(); lab[tmp[0]] = tmp[2]; lab[tmp[1]] = tmp[3]; connected--; } } } dsu; vector<ii> event[N]; vector<int> up[N], down[N], upB[N], downB[N]; vector<int> queries[N]; vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) { n = N; c = T.size(); q = W.size(); REP(i, c) if (X[i] > Y[i]) swap(X[i], Y[i]); vector<int> query; REP(i, q) query.pb(i); sort(all(query), [&](int &x, int &y){ return W[x] < W[y]; }); vector<int> res(q, 0); int Q = 0; for(int B = 0; B < c; B += S) { int L = B, R = min(c, B + S) - 1; int _Q = Q; for(; _Q < q && W[query[_Q]] <= R; _Q++) { int i_q = query[_Q]; queries[P[i_q]].pb(i_q); } vector<bool> up_check(n, false), down_check(n, false); vector<int> ups, downs; FOR(i, L, R) { if (up_check[Y[i]] == false) { ups.pb(Y[i]); up_check[Y[i]] = true; } if (down_check[X[i]] == false) { downs.pb(X[i]); down_check[X[i]] = true; } upB[Y[i]].pb(i); downB[X[i]].pb(i); } sort(all(ups)); sort(all(downs), greater<int>()); // answer query up dsu = DSU(n); REP(w, n) { for(int &i : up[w]) dsu.unite(X[i], Y[i]); dsu.history.clear(); for(int &i_q : queries[w]) { for(int &i : ups) { if (i > w) break; for(int &j : upB[i]) if (j <= W[i_q]) dsu.unite(X[j], Y[j]); } res[i_q] += w + 1 - dsu.connected; // scc with index <= p dsu.roll_back(); } } // answer query down dsu = DSU(n); RED(w, n) { for(int &i_q : queries[w]) { for(int &i : downs) { if (i <= w) break; for(int &j : downB[i]) if (j <= W[i_q]) dsu.unite(X[j], Y[j]); } res[i_q] += n - (w + 1) - dsu.connected; dsu.roll_back(); } for(int &i : down[w]) dsu.unite(X[i], Y[i]); dsu.history.clear(); } // clear query + add edge in current block for(; Q < _Q; Q++) { int i_q = query[Q]; queries[P[i_q]].clear(); } FOR(i, L, R) { up[Y[i]].pb(i); down[X[i]].pb(i); } } return res; } // int main() { // ios_base::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // auto ans = simulateCollapse(5, {0, 0, 0, 0, 0, 0, 0}, {3, 4, 2, 2, 2, 2, 4}, {1, 1, 3, 1, 4, 0, 0}, // {5, 5, 5, 5, 5}, {0, 1, 2, 3, 4}); // for(int x : ans) cout << x << ' '; cout << '\n'; // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...