제출 #65799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65799		Benq	Collapse (JOI18_collapse)	C++14	100 / 100	5231 ms	83760 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;
    }
};

vi ans;
vector<array<int,3>> change;
vpi tri[MX];
unordered_set<int> from[MX], to[MX];
 
unordered_map<ll,int> u;
vpi ru;

ll hsh(pi cur) { return (ll)cur.f*MX+cur.s; }

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,bitset<BLOCK>>> 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;
        	F0R(j,sz(ru)) if (todo[ind].s[j] == 1 && ru[j].s <= i)
        		tmp.pb({A.get(ru[j].f),A.get(ru[j].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;
        	F0R(j,sz(ru)) if (todo[ind].s[j] == 1 && ru[j].f >= N-1-i)
        		tmp.pb({B.get(ru[j].f),B.get(ru[j].s)});
        		
        	ans[todo[ind].f.s] -= mini(tmp);
        	ind ++;
        }
    }
}
 
void genDSU() {
    sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
    solveA();
    reverse(all(todo)); 
    solveB();
	todo.clear();
}

void process(int l, int r) {
	u.clear(), ru.clear();
	bitset<BLOCK> b = bitset<BLOCK>();
    FOR(i,l,r+1) {
        pi cur = {change[i][1],change[i][2]};
        if (!u.count((ll)cur.f*MX+cur.s)) {
        	int t = sz(u);
        	u[hsh(cur)] = t;
        	ru.pb(cur);
        }
        if (from[cur.f].count(cur.s)) {
        	from[cur.f].erase(cur.s); to[cur.s].erase(cur.f);
            b[u[hsh(cur)]] = 1;
        }
    }
    FOR(i,l,r+1) {
        pi cur = {change[i][1],change[i][2]};
        if (change[i][0] == 0) b[u[hsh(cur)]] = 1;
        else b[u[hsh(cur)]] = 0;
        for (auto a: tri[i]) todo.pb({a,b});
    }
    genDSU();
    F0R(i,sz(ru)) if (b[i] == 1) {
    	pi a = ru[i];
    	from[a.f].insert(a.s), to[a.s].insert(a.f);
    }
}
 
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: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35