oj.uz

Submission #65797

# Submission time Handle Problem Language Result Execution time Memory
65797 2018-08-08T21:33:17 Z Benq Collapse (JOI18_collapse) C++11
5 / 100
 12149 ms 525312 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 = 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14584 KB Output is correct
2 Correct 19 ms 15008 KB Output is correct
3 Correct 27 ms 16308 KB Output is correct
4 Correct 52 ms 20092 KB Output is correct
5 Correct 30 ms 20092 KB Output is correct
6 Correct 579 ms 39232 KB Output is correct
7 Correct 19 ms 39232 KB Output is correct
8 Correct 29 ms 39232 KB Output is correct
9 Correct 45 ms 39232 KB Output is correct
10 Correct 366 ms 39232 KB Output is correct
11 Correct 617 ms 39232 KB Output is correct
12 Correct 597 ms 39444 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 39444 KB Output is correct
2 Correct 123 ms 39444 KB Output is correct
3 Correct 549 ms 39444 KB Output is correct
4 Correct 668 ms 131072 KB Output is correct
5 Correct 6043 ms 131072 KB Output is correct
6 Correct 11364 ms 494156 KB Output is correct
7 Correct 12149 ms 494156 KB Output is correct
8 Correct 7502 ms 494156 KB Output is correct
9 Correct 103 ms 494156 KB Output is correct
10 Correct 231 ms 494156 KB Output is correct
11 Runtime error 2610 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14584 KB Output is correct
2 Correct 19 ms 15008 KB Output is correct
3 Correct 27 ms 16308 KB Output is correct
4 Correct 52 ms 20092 KB Output is correct
5 Correct 30 ms 20092 KB Output is correct
6 Correct 579 ms 39232 KB Output is correct
7 Correct 19 ms 39232 KB Output is correct
8 Correct 29 ms 39232 KB Output is correct
9 Correct 45 ms 39232 KB Output is correct
10 Correct 366 ms 39232 KB Output is correct
11 Correct 617 ms 39232 KB Output is correct
12 Correct 597 ms 39444 KB Output is correct
13 Correct 77 ms 39444 KB Output is correct
14 Correct 123 ms 39444 KB Output is correct
15 Correct 549 ms 39444 KB Output is correct
16 Correct 668 ms 131072 KB Output is correct
17 Correct 6043 ms 131072 KB Output is correct
18 Correct 11364 ms 494156 KB Output is correct
19 Correct 12149 ms 494156 KB Output is correct
20 Correct 7502 ms 494156 KB Output is correct
21 Correct 103 ms 494156 KB Output is correct
22 Correct 231 ms 494156 KB Output is correct
23 Runtime error 2610 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -