Submission #1261636

#TimeUsernameProblemLanguageResultExecution timeMemory
1261636icebearCollapse (JOI18_collapse)C++20
0 / 100
129 ms5312 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 scc; DSU(int n = 0): lab(n, -1), scc(n) {} 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]}); scc--; 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]; scc++; } } } dsu; vector<ii> event[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(); vector<ii> query; REP(i, q) query.pb(mp(W[i], i)); sort(all(query)); vector<int> res(q, 0); dsu = DSU(n); int Q = 0; for(int B = 0; B < c; B += S) { int L = B, R = min(c, B + S) - 1; for(; Q < q && query[Q].fi <= R; Q++) { int upper = P[query[Q].se]; int lower = P[query[Q].se] + 1; FOR(i, L, query[Q].fi) if (max(X[i], Y[i]) <= upper || min(X[i], Y[i]) >= lower) dsu.unite(X[i], Y[i]); res[query[Q].se] = dsu.scc; dsu.roll_back(); } FOR(i, L, R) dsu.unite(X[i], Y[i]); dsu.history.clear(); } 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, 1, 2, 4}, {1, 3, 4, 0}, {3}, {1}); // for(int x : ans) cout << x << ' '; cout << '\n'; // // 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}, {1}, {0}); // // 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...