제출 #1215488

#제출 시각아이디문제언어결과실행 시간메모리
1215488JooDdaeCollapse (JOI18_collapse)C++20
35 / 100
15085 ms16672 KiB
#include "collapse.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int sq = 350; struct UnionFind { vector<int> P, S; int N, sz; vector<array<int, 2>> rb; UnionFind(int N): N(N), P(N), S(N, 1), rb(N), sz(0) { iota(P.begin(), P.end(), 0); } int find(int x) { return x == P[x] ? x : find(P[x]); } void merge(int x, int y) { if((x = find(x)) == (y = find(y))) return; if(S[x] > S[y]) swap(x, y); S[y] += S[x], P[x] = P[y]; rb[sz++] = {x, y}; } void rollBack(int k) { while(sz > k) { auto [x, y] = rb[--sz]; S[y] -= S[x], P[x] = x; } } }; void solve(int N, int M, vector<int> &T, vector<int> &X, vector<int> &Y, vector<int> &W, vector<int> &P, vector<int> &re) { int K = X.size(); int C = (K-1)/sq+1; vector<vector<array<int, 3>>> Q(C); for(int i=0;i<M;i++) Q[W[i]/sq].push_back({P[i], W[i], i}); vector<array<int, 3>> V(K); for(int i=0;i<K;i++) V[i] = {min(X[i], Y[i]), max(X[i], Y[i]), i}; sort(V.begin(), V.end()); vector<array<int, 4>> E; for(int i=0;i<K;i++) { auto [x, y, t] = V[i]; int j = i; while(j+1 < K && V[j+1][0] == x && V[j+1][1] == y) j++; for(int k=i;k<=j;k+=2) E.push_back({x, y, V[k][2], k == j ? K : V[k+1][2]-1}); i = j; } for(int i=0;i<C;i++) { int L = i*sq, R = min(L+sq-1, K-1); vector<vector<int>> s(N); vector<array<int, 4>> sp; for(auto [x, y, l, r] : E) { if(l <= L && R <= r) s[y].push_back(x); else if(L <= r || l <= R) sp.push_back({x, y, l, r}); } sort(Q[i].begin(), Q[i].end()); UnionFind uf(N); for(int j=0, k=0;j<N-1;j++) { for(auto L : s[j]) uf.merge(L, j); while(k < Q[i].size() && Q[i][k][0] == j) { auto [P, W, id] = Q[i][k++]; int rev = uf.sz; for(auto [x, y, l, r] : sp) if(l <= W && W <= r && max(x, y) <= P) uf.merge(x, y); re[id] -= uf.sz; uf.rollBack(rev); } } } } vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) { int M = W.size(); vector<int> re(M, N); solve(N, M, T, X, Y, W, P, re); for(int i=0;i<X.size();i++) X[i] = N-X[i]-1, Y[i] = N-Y[i]-1; for(int i=0;i<M;i++) P[i] = N-P[i]-2; solve(N, M, T, X, Y, W, P, re); return re; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...