oj.uz

Submission #65796

# Submission time Handle Problem Language Result Execution time Memory
65796 2018-08-08T20:59:35 Z Benq Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 91484 KB 
#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 = 1500;

int N;

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});
        }
    }
};

DSU A,B;
vi ans;
vector<array<int,3>> change;
vpi tri[MX];
unordered_set<int> from[MX], to[MX];
set<pi> tedge;

void genDSU() {
    A = B = DSU();
    
    F0R(i,N) {
        B.numComp[i] = (i?B.numComp[i-1]:0)+1;
        for (int x: from[N-1-i]) B.unite(i,x,N-1-i);
    }
    
    F0R(i,N) {
        A.numComp[i] = (i?A.numComp[i-1]:0)+1;
    	for (int x: to[i]) A.unite(i,x,i);
    }
    
}

int m[MX];

struct realDSU {
    int par[2*BLOCK];
    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;
        return 1;
    }
};

realDSU 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;
}

int solve(int x) {
    int t0 = x, t1 = N-1-(x+1);
    int ret = A.getComp(t0)+B.getComp(t1);
    vpi ed[2];
    for (auto a: tedge) {
        if (a.s <= x) {
            ed[0].pb({A.get(t0,a.f),A.get(t0,a.s)});
        } else if (a.f >= x+1) {
            ed[1].pb({B.get(t1,a.f),B.get(t1,a.s)});
        }
    }
    int ans = ret-mini(ed[0])-mini(ed[1]);
    return ans;
}

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);
        }
    }
    genDSU();
    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]) ans[a.s] = solve(a.f);
    }
    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;
	// 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);
	}
}

#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 28920 KB Output is correct
2 Correct 36 ms 28920 KB Output is correct
3 Correct 36 ms 28920 KB Output is correct
4 Correct 33 ms 28956 KB Output is correct
5 Correct 53 ms 29164 KB Output is correct
6 Correct 164 ms 29688 KB Output is correct
7 Correct 34 ms 29688 KB Output is correct
8 Correct 35 ms 29688 KB Output is correct
9 Correct 70 ms 30128 KB Output is correct
10 Correct 228 ms 30388 KB Output is correct
11 Correct 320 ms 30964 KB Output is correct
12 Correct 264 ms 30964 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 31904 KB Output is correct
2 Correct 61 ms 32372 KB Output is correct
3 Correct 436 ms 37916 KB Output is correct
4 Correct 145 ms 37916 KB Output is correct
5 Correct 857 ms 38224 KB Output is correct
6 Correct 1856 ms 38224 KB Output is correct
7 Correct 3277 ms 47100 KB Output is correct
8 Correct 1020 ms 47100 KB Output is correct
9 Correct 94 ms 47100 KB Output is correct
10 Correct 139 ms 47100 KB Output is correct
11 Correct 1291 ms 47100 KB Output is correct
12 Correct 2260 ms 57392 KB Output is correct
13 Correct 10127 ms 71364 KB Output is correct
14 Execution timed out 15023 ms 81584 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 81584 KB Output is correct
2 Correct 87 ms 81584 KB Output is correct
3 Correct 112 ms 81584 KB Output is correct
4 Correct 165 ms 81584 KB Output is correct
5 Correct 1320 ms 81584 KB Output is correct
6 Correct 2417 ms 81584 KB Output is correct
7 Correct 3719 ms 81584 KB Output is correct
8 Correct 6740 ms 81584 KB Output is correct
9 Correct 106 ms 81584 KB Output is correct
10 Correct 3016 ms 81584 KB Output is correct
11 Execution timed out 15042 ms 91484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 28920 KB Output is correct
2 Correct 36 ms 28920 KB Output is correct
3 Correct 36 ms 28920 KB Output is correct
4 Correct 33 ms 28956 KB Output is correct
5 Correct 53 ms 29164 KB Output is correct
6 Correct 164 ms 29688 KB Output is correct
7 Correct 34 ms 29688 KB Output is correct
8 Correct 35 ms 29688 KB Output is correct
9 Correct 70 ms 30128 KB Output is correct
10 Correct 228 ms 30388 KB Output is correct
11 Correct 320 ms 30964 KB Output is correct
12 Correct 264 ms 30964 KB Output is correct
13 Correct 62 ms 31904 KB Output is correct
14 Correct 61 ms 32372 KB Output is correct
15 Correct 436 ms 37916 KB Output is correct
16 Correct 145 ms 37916 KB Output is correct
17 Correct 857 ms 38224 KB Output is correct
18 Correct 1856 ms 38224 KB Output is correct
19 Correct 3277 ms 47100 KB Output is correct
20 Correct 1020 ms 47100 KB Output is correct
21 Correct 94 ms 47100 KB Output is correct
22 Correct 139 ms 47100 KB Output is correct
23 Correct 1291 ms 47100 KB Output is correct
24 Correct 2260 ms 57392 KB Output is correct
25 Correct 10127 ms 71364 KB Output is correct
26 Execution timed out 15023 ms 81584 KB Time limit exceeded
27 Halted 0 ms 0 KB -