oj.uz

Submission #65795

# Submission time Handle Problem Language Result Execution time Memory
65795 2018-08-08T20:40:25 Z Benq Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 89540 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 = 600;

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];
set<pi> cedge, tedge;
vi st[MX], en[MX];

void genDSU() {
    F0R(i,N) st[i].clear(), en[i].clear();
    for (auto a: cedge) {
        st[a.f].pb(a.s);
        en[a.s].pb(a.f);
    }
    A = DSU(), B = DSU();
    F0R(i,N) {
        A.numComp[i] = (i?A.numComp[i-1]:0)+1;
        for (auto a: en[i]) A.unite(i,a,i);
    }
    // cout << "OH " << A.numComp[4] << " " << A.get(0,4) << "\n";
    F0R(i,N) {
        B.numComp[i] = (i?B.numComp[i-1]:0)+1;
        for (auto a: st[N-1-i]) B.unite(i,a,N-1-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 ++;
    // cout << "AH " << co << " " << res << "\n";
    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) {
        // cout << "HA " << t0 << " " << t1 << " " << a.f << " " << a.s << "\n";
        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)});
        }
    }
    // return 0;
    int ans = ret-mini(ed[0])-mini(ed[1]);
    /*cout << "HUH " << x << " " << ret << " " << sz(ed[0]) << " " << sz(ed[1]) << " " << ans << "\n";
    if (sz(ed[0])) cout << ed[0][0].f << " " << ed[0][0].s << "\n";
    if (sz(ed[1])) cout << ed[1][0].f << " " << ed[1][0].s << "\n";*/
    return ans;
}

void process(int l, int r) {
    FOR(i,l,r+1) {
        pi cur = {change[i][1],change[i][2]};
        if (cedge.count(cur)) {
            cedge.erase(cur); 
            tedge.insert(cur);
        }
    }
    genDSU();
    FOR(i,l,r+1) {
        pi cur = {change[i][1],change[i][2]};
        // cout << "HUH " << i << " " << cur.f << " " << cur.s << "\n";
        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) cedge.insert(a);
    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;
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	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 69 ms 27512 KB Output is correct
2 Correct 33 ms 27512 KB Output is correct
3 Correct 36 ms 27512 KB Output is correct
4 Correct 38 ms 27512 KB Output is correct
5 Correct 93 ms 27864 KB Output is correct
6 Correct 134 ms 28308 KB Output is correct
7 Correct 32 ms 28512 KB Output is correct
8 Correct 33 ms 28608 KB Output is correct
9 Correct 97 ms 29156 KB Output is correct
10 Correct 146 ms 29388 KB Output is correct
11 Correct 218 ms 30216 KB Output is correct
12 Correct 186 ms 30216 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 31608 KB Output is correct
2 Correct 68 ms 32488 KB Output is correct
3 Correct 1063 ms 39436 KB Output is correct
4 Correct 148 ms 39436 KB Output is correct
5 Correct 1641 ms 41608 KB Output is correct
6 Correct 875 ms 41608 KB Output is correct
7 Correct 3051 ms 50356 KB Output is correct
8 Correct 2348 ms 50356 KB Output is correct
9 Correct 98 ms 53720 KB Output is correct
10 Correct 128 ms 54708 KB Output is correct
11 Correct 948 ms 62636 KB Output is correct
12 Correct 9493 ms 70572 KB Output is correct
13 Execution timed out 15010 ms 77080 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 77080 KB Output is correct
2 Correct 77 ms 77080 KB Output is correct
3 Correct 120 ms 77080 KB Output is correct
4 Correct 161 ms 77080 KB Output is correct
5 Correct 1314 ms 77080 KB Output is correct
6 Correct 1066 ms 77080 KB Output is correct
7 Correct 2323 ms 77080 KB Output is correct
8 Correct 6055 ms 77080 KB Output is correct
9 Correct 110 ms 77080 KB Output is correct
10 Correct 1643 ms 77080 KB Output is correct
11 Execution timed out 15012 ms 89540 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 27512 KB Output is correct
2 Correct 33 ms 27512 KB Output is correct
3 Correct 36 ms 27512 KB Output is correct
4 Correct 38 ms 27512 KB Output is correct
5 Correct 93 ms 27864 KB Output is correct
6 Correct 134 ms 28308 KB Output is correct
7 Correct 32 ms 28512 KB Output is correct
8 Correct 33 ms 28608 KB Output is correct
9 Correct 97 ms 29156 KB Output is correct
10 Correct 146 ms 29388 KB Output is correct
11 Correct 218 ms 30216 KB Output is correct
12 Correct 186 ms 30216 KB Output is correct
13 Correct 56 ms 31608 KB Output is correct
14 Correct 68 ms 32488 KB Output is correct
15 Correct 1063 ms 39436 KB Output is correct
16 Correct 148 ms 39436 KB Output is correct
17 Correct 1641 ms 41608 KB Output is correct
18 Correct 875 ms 41608 KB Output is correct
19 Correct 3051 ms 50356 KB Output is correct
20 Correct 2348 ms 50356 KB Output is correct
21 Correct 98 ms 53720 KB Output is correct
22 Correct 128 ms 54708 KB Output is correct
23 Correct 948 ms 62636 KB Output is correct
24 Correct 9493 ms 70572 KB Output is correct
25 Execution timed out 15010 ms 77080 KB Time limit exceeded
26 Halted 0 ms 0 KB -