답안 #65799 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65799	2018-08-08T21:44:27 Z	Benq	Collapse (JOI18_collapse)	C++14	100 / 100	5231 ms	83760 KB

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

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	14708 KB	Output is correct
2	Correct	19 ms	15232 KB	Output is correct
3	Correct	22 ms	15232 KB	Output is correct
4	Correct	23 ms	15272 KB	Output is correct
5	Correct	25 ms	15272 KB	Output is correct
6	Correct	87 ms	15368 KB	Output is correct
7	Correct	22 ms	15472 KB	Output is correct
8	Correct	20 ms	15472 KB	Output is correct
9	Correct	38 ms	15472 KB	Output is correct
10	Correct	130 ms	15472 KB	Output is correct
11	Correct	136 ms	15576 KB	Output is correct
12	Correct	204 ms	15576 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	34904 KB	Output is correct
2	Correct	117 ms	34904 KB	Output is correct
3	Correct	295 ms	34904 KB	Output is correct
4	Correct	187 ms	34904 KB	Output is correct
5	Correct	1077 ms	34904 KB	Output is correct
6	Correct	1345 ms	34904 KB	Output is correct
7	Correct	2660 ms	34904 KB	Output is correct
8	Correct	1059 ms	34904 KB	Output is correct
9	Correct	96 ms	34904 KB	Output is correct
10	Correct	127 ms	34904 KB	Output is correct
11	Correct	1059 ms	35120 KB	Output is correct
12	Correct	1199 ms	35120 KB	Output is correct
13	Correct	3056 ms	35120 KB	Output is correct
14	Correct	3965 ms	35120 KB	Output is correct
15	Correct	3566 ms	37456 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	37720 KB	Output is correct
2	Correct	106 ms	37720 KB	Output is correct
3	Correct	144 ms	37720 KB	Output is correct
4	Correct	188 ms	37720 KB	Output is correct
5	Correct	1195 ms	37720 KB	Output is correct
6	Correct	1424 ms	37720 KB	Output is correct
7	Correct	2198 ms	37720 KB	Output is correct
8	Correct	3331 ms	37720 KB	Output is correct
9	Correct	116 ms	37772 KB	Output is correct
10	Correct	2185 ms	37772 KB	Output is correct
11	Correct	4920 ms	37772 KB	Output is correct
12	Correct	4825 ms	39116 KB	Output is correct
13	Correct	4921 ms	41072 KB	Output is correct
14	Correct	4614 ms	44176 KB	Output is correct
15	Correct	4787 ms	46256 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	14708 KB	Output is correct
2	Correct	19 ms	15232 KB	Output is correct
3	Correct	22 ms	15232 KB	Output is correct
4	Correct	23 ms	15272 KB	Output is correct
5	Correct	25 ms	15272 KB	Output is correct
6	Correct	87 ms	15368 KB	Output is correct
7	Correct	22 ms	15472 KB	Output is correct
8	Correct	20 ms	15472 KB	Output is correct
9	Correct	38 ms	15472 KB	Output is correct
10	Correct	130 ms	15472 KB	Output is correct
11	Correct	136 ms	15576 KB	Output is correct
12	Correct	204 ms	15576 KB	Output is correct
13	Correct	78 ms	34904 KB	Output is correct
14	Correct	117 ms	34904 KB	Output is correct
15	Correct	295 ms	34904 KB	Output is correct
16	Correct	187 ms	34904 KB	Output is correct
17	Correct	1077 ms	34904 KB	Output is correct
18	Correct	1345 ms	34904 KB	Output is correct
19	Correct	2660 ms	34904 KB	Output is correct
20	Correct	1059 ms	34904 KB	Output is correct
21	Correct	96 ms	34904 KB	Output is correct
22	Correct	127 ms	34904 KB	Output is correct
23	Correct	1059 ms	35120 KB	Output is correct
24	Correct	1199 ms	35120 KB	Output is correct
25	Correct	3056 ms	35120 KB	Output is correct
26	Correct	3965 ms	35120 KB	Output is correct
27	Correct	3566 ms	37456 KB	Output is correct
28	Correct	78 ms	37720 KB	Output is correct
29	Correct	106 ms	37720 KB	Output is correct
30	Correct	144 ms	37720 KB	Output is correct
31	Correct	188 ms	37720 KB	Output is correct
32	Correct	1195 ms	37720 KB	Output is correct
33	Correct	1424 ms	37720 KB	Output is correct
34	Correct	2198 ms	37720 KB	Output is correct
35	Correct	3331 ms	37720 KB	Output is correct
36	Correct	116 ms	37772 KB	Output is correct
37	Correct	2185 ms	37772 KB	Output is correct
38	Correct	4920 ms	37772 KB	Output is correct
39	Correct	4825 ms	39116 KB	Output is correct
40	Correct	4921 ms	41072 KB	Output is correct
41	Correct	4614 ms	44176 KB	Output is correct
42	Correct	4787 ms	46256 KB	Output is correct
43	Correct	771 ms	46256 KB	Output is correct
44	Correct	3340 ms	48100 KB	Output is correct
45	Correct	1272 ms	48100 KB	Output is correct
46	Correct	3218 ms	53008 KB	Output is correct
47	Correct	126 ms	56768 KB	Output is correct
48	Correct	140 ms	57252 KB	Output is correct
49	Correct	1259 ms	58944 KB	Output is correct
50	Correct	2158 ms	58944 KB	Output is correct
51	Correct	1608 ms	58944 KB	Output is correct
52	Correct	3275 ms	58944 KB	Output is correct
53	Correct	3672 ms	58944 KB	Output is correct
54	Correct	3815 ms	63744 KB	Output is correct
55	Correct	4483 ms	65876 KB	Output is correct
56	Correct	4837 ms	69860 KB	Output is correct
57	Correct	5231 ms	74052 KB	Output is correct
58	Correct	4288 ms	76984 KB	Output is correct
59	Correct	4886 ms	80648 KB	Output is correct
60	Correct	5022 ms	83760 KB	Output is correct

답안 #65799

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 30.0 / 30.0

Subtask #3 30.0 / 30.0

Subtask #4 35.0 / 35.0

Subtask #1
5.0 / 5.0

Subtask #2
30.0 / 30.0

Subtask #3
30.0 / 30.0

Subtask #4
35.0 / 35.0