Submission #65797

#	Time	Username	Problem	Language	Result	Execution time	Memory
65797		Benq	Collapse (JOI18_collapse)	C++11	5 / 100	12149 ms	525312 KiB

collapse

#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
*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35