Submission #65797

#TimeUsernameProblemLanguageResultExecution timeMemory
65797BenqCollapse (JOI18_collapse)C++11
5 / 100
12149 ms525312 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; // #define LOCAL #ifdef LOCAL #else #include "collapse.h" #endif const int BLOCK = 1000; int N; template<int SZ> struct realDSU { int par[SZ], numComp = 0; void init(int co) { F0R(i,co) par[i] = i; } int get(int x) { // path compression if (par[x] != x) par[x] = get(par[x]); return par[x]; } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return 0; if (rand()&1) swap(x,y); par[y] = x; numComp --; return 1; } }; struct DSU { // persistent DSU vpi par[MX], child[MX]; int numComp[MX]; DSU() { F0R(i,N) { par[i].pb({-1,i}); child[i].pb({-1,i}); } } int getComp(int ti) { return numComp[ti]; } int get(int ti, int x) { return prev(ub(all(par[x]),mp(ti,MOD)))->s; } void unite(int ti, int x, int y) { x = par[x].back().s, y = par[y].back().s; if (x == y) return; numComp[ti] --; if (sz(child[x]) < sz(child[y])) swap(x,y); for (auto a: child[y]) { par[a.s].pb({ti,x}); child[x].pb({ti,a.s}); } } }; vi ans; vector<array<int,3>> change; vpi tri[MX]; unordered_set<int> from[MX], to[MX]; set<pi> tedge; int m[MX]; realDSU<2*BLOCK> R; int mini(const vpi& v) { int co = 0; for (auto a: v) m[a.f] = m[a.s] = -1; for (auto a: v) { if (m[a.f] == -1) m[a.f] = co ++; if (m[a.s] == -1) m[a.s] = co ++; } R.init(co); int res = 0; for (auto a: v) if (R.unite(m[a.f],m[a.s])) res ++; return res; } vector<pair<pi,set<pi>>> todo; void solveA() { realDSU<MX> A = realDSU<MX>(); A.init(N); int ind = 0; F0R(i,N) { A.numComp ++; for (int x: to[i]) A.unite(x,i); while (ind < sz(todo) && todo[ind].f.f == i) { ans[todo[ind].f.s] += A.numComp; vpi tmp; for (auto z: todo[ind].s) if (z.s <= i) tmp.pb({A.get(z.f),A.get(z.s)}); ans[todo[ind].f.s] -= mini(tmp); ind ++; } } } void solveB() { realDSU<MX> B = realDSU<MX>(); B.init(N); int ind = 0; F0R(i,N) { B.numComp ++; for (int x: from[N-1-i]) B.unite(x,N-1-i); while (ind < sz(todo) && todo[ind].f.f+1 == N-1-i) { ans[todo[ind].f.s] += B.numComp; vpi tmp; for (auto z: todo[ind].s) if (z.f >= N-1-i) tmp.pb({B.get(z.f),B.get(z.s)}); ans[todo[ind].f.s] -= mini(tmp); ind ++; } } } void genDSU() { sort(all(todo)); solveA(); reverse(all(todo)); solveB(); todo.clear(); } void process(int l, int r) { FOR(i,l,r+1) { pi cur = {change[i][1],change[i][2]}; if (from[cur.f].count(cur.s)) { from[cur.f].erase(cur.s); to[cur.s].erase(cur.f); tedge.insert(cur); } } FOR(i,l,r+1) { pi cur = {change[i][1],change[i][2]}; if (change[i][0] == 0) tedge.insert(cur); else tedge.erase(cur); for (auto a: tri[i]) todo.pb({a,tedge}); } genDSU(); for (auto a: tedge) from[a.f].insert(a.s), to[a.s].insert(a.f); tedge.clear(); } vi simulateCollapse(int n, vi T, vi X, vi Y, vi W, vi P) { N = n; F0R(i,sz(X)) { if (X[i] > Y[i]) swap(X[i],Y[i]); change.pb({T[i],X[i],Y[i]}); } ans.resize(sz(W)); F0R(i,sz(ans)) tri[W[i]].pb({P[i],i}); for (int i = 0; i < sz(X); i += BLOCK) process(i,min(i+BLOCK,sz(X))-1); return ans; } #ifdef LOCAL int main(int argc, char *argv[]) { int N, C, Q; //cin >> N; //C = Q = N; scanf("%d%d%d", &N, &C, &Q); std::vector<int> T(C), X(C), Y(C); for(int i = 0; i < C; i++) { // T[i] = 0; X[i] = rand() % N, Y[i] = rand() % N; scanf("%d%d%d", &T[i], &X[i], &Y[i]); } std::vector<int> W(Q), P(Q); for(int i = 0; i < Q; i++) { // W[i] = rand() % N; P[i] = rand() % (N-1); scanf("%d%d", &W[i], &P[i]); } auto res = simulateCollapse(N, T, X, Y, W, P); printf("%d\n",Q); for(auto i : res) { printf("%d\n", i); } } /* 5 8 2 0 0 1 0 1 3 0 2 4 0 4 0 1 1 3 0 0 3 0 1 2 0 4 3 3 1 7 3 */ #endif /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...