답안 #67619 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67619	2018-08-15T06:48:16 Z	top34051	Collapse (JOI18_collapse)	C++17	100 / 100	8042 ms	287872 KB

collapse

//subtask3
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int sq = 320;

class DSU {
public:
	int n,com;
	int head[maxn], sz[maxn];
	stack<pii> stk;

	void init(int _n) {
		n = com = _n;
		for(int i=0;i<n;i++) {
			head[i] = i;
			sz[i] = 1;
		}
	}

	int findhead(int x) {
		if(x==head[x]) return x;
		return findhead(head[x]);
	}

	void add_edge(int u, int v) {
		int x = findhead(u), y = findhead(v);
		if(sz[x] > sz[y]) swap(x,y);
		stk.push({x,y});
		if(x!=y) {
			head[x] = y;
			sz[y] += sz[x];
			com--;
		}
	}

	void pop_edge() {
		int x = stk.top().X, y = stk.top().Y; stk.pop();
		if(x!=y) {
            head[x] = x;
            sz[y] -= sz[x];
            com++;
		}
	}

	int size() {
	    return com;
	}
} dsu;

struct trp {
	int x,y,id;
};

int n,m,q;
int ft[maxn];
map<pii,int> occur;

vector<trp> op;
vector<int> good, amb;
vector<int> ask[maxn];
int ans[maxn];

bool cmpL(trp a, trp b) {
    if(a.y != b.y) return a.y < b.y;
    return a.id < b.id;
}

bool cmpR(trp a, trp b) {
    if(a.x != b.x) return a.x > b.x;
    return a.id < b.id;
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> D, vector<int> P) {
	n = N; m = T.size(); q = D.size();
	for(int i=0;i<m;i++) {
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		if(T[i]==0) {
			ft[i] = m-1;
			occur[{X[i],Y[i]}] = i;
		}
		else ft[occur[{X[i],Y[i]}]] = i-1;
	}

	for(int i=0;i<q;i++) ask[D[i]].push_back(i);

	for(int s=0;s<m;s+=sq) {
		int e = min(m,s+sq-1);

		//eliminate all invalid edge (ft[i] < s)
		vector<int> tmp;
		for(auto i : good) {
			if(ft[i] < s) continue;
			tmp.push_back(i);
		}
		good = tmp;

		//---------------------------------------------------------------------------

		op.clear(); amb.clear();
		for(int i=s;i<=e;i++) {
			for(auto x : ask[i]) op.push_back({P[x],P[x],x});
		}
		for(auto i : good) {
			if(ft[i]>=e) op.push_back({X[i],Y[i],-1});
			else amb.push_back(i);
		}
		for(int i=s;i<=e;i++) amb.push_back(i);

		sort(op.begin(),op.end(),cmpL);

		dsu.init(n);
		for(auto t : op) {
			int x = t.id;
			if(x<0) dsu.add_edge(t.x,t.y);
			else {
				int ex = 0;
				for(auto i : amb) {
					if(Y[i]<=t.x && i<=D[x] && D[x]<=ft[i]) {
						dsu.add_edge(X[i],Y[i]);
						ex++;
					}
				}
				ans[x] += dsu.size();
				while(ex--) dsu.pop_edge();
			}
		}

		//---------------------------------------------------------------------------

		op.clear();
		for(int i=s;i<=e;i++) {
			for(auto x : ask[i]) op.push_back({P[x]+1,P[x]+1,x});
		}
		for(auto i : good) {
			if(ft[i]>=e) op.push_back({X[i],Y[i],-1});
			else amb.push_back(i);
		}

		sort(op.begin(),op.end(),cmpR);

		dsu.init(n);
		for(auto t : op) {
			int x = t.id;
			if(x<0) dsu.add_edge(t.x,t.y);
			else {
				int ex = 0;
				for(auto i : amb) {
					if(t.y<=X[i] && i<=D[x] && D[x]<=ft[i]) {
						dsu.add_edge(X[i],Y[i]);
						ex++;
					}
				}
				ans[x] += dsu.size();
				while(ex--) dsu.pop_edge();
			}
		}

		//---------------------------------------------------------------------------

		for(int i=s;i<=e;i++) {
			if(T[i]==0) good.push_back(i);
		}

	}

	vector<int> vec;
	for(int i=0;i<q;i++) vec.push_back(ans[i]-n);
	return vec;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	3064 KB	Output is correct
2	Correct	9 ms	3064 KB	Output is correct
3	Correct	12 ms	3064 KB	Output is correct
4	Correct	10 ms	3176 KB	Output is correct
5	Correct	29 ms	3348 KB	Output is correct
6	Correct	60 ms	4464 KB	Output is correct
7	Correct	9 ms	4464 KB	Output is correct
8	Correct	11 ms	4464 KB	Output is correct
9	Correct	31 ms	4464 KB	Output is correct
10	Correct	51 ms	4464 KB	Output is correct
11	Correct	103 ms	5092 KB	Output is correct
12	Correct	72 ms	5220 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	8040 KB	Output is correct
2	Correct	70 ms	8108 KB	Output is correct
3	Correct	387 ms	13472 KB	Output is correct
4	Correct	128 ms	13472 KB	Output is correct
5	Correct	629 ms	15640 KB	Output is correct
6	Correct	715 ms	15640 KB	Output is correct
7	Correct	5371 ms	279020 KB	Output is correct
8	Correct	584 ms	279020 KB	Output is correct
9	Correct	58 ms	279020 KB	Output is correct
10	Correct	103 ms	279020 KB	Output is correct
11	Correct	498 ms	279020 KB	Output is correct
12	Correct	725 ms	279020 KB	Output is correct
13	Correct	3001 ms	279020 KB	Output is correct
14	Correct	7515 ms	279900 KB	Output is correct
15	Correct	6533 ms	279900 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	279900 KB	Output is correct
2	Correct	84 ms	279900 KB	Output is correct
3	Correct	113 ms	279900 KB	Output is correct
4	Correct	109 ms	279900 KB	Output is correct
5	Correct	573 ms	279900 KB	Output is correct
6	Correct	987 ms	279900 KB	Output is correct
7	Correct	3623 ms	279900 KB	Output is correct
8	Correct	6861 ms	279900 KB	Output is correct
9	Correct	91 ms	279900 KB	Output is correct
10	Correct	556 ms	279900 KB	Output is correct
11	Correct	7164 ms	279900 KB	Output is correct
12	Correct	8042 ms	279900 KB	Output is correct
13	Correct	7087 ms	279900 KB	Output is correct
14	Correct	7898 ms	279900 KB	Output is correct
15	Correct	6620 ms	279900 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	3064 KB	Output is correct
2	Correct	9 ms	3064 KB	Output is correct
3	Correct	12 ms	3064 KB	Output is correct
4	Correct	10 ms	3176 KB	Output is correct
5	Correct	29 ms	3348 KB	Output is correct
6	Correct	60 ms	4464 KB	Output is correct
7	Correct	9 ms	4464 KB	Output is correct
8	Correct	11 ms	4464 KB	Output is correct
9	Correct	31 ms	4464 KB	Output is correct
10	Correct	51 ms	4464 KB	Output is correct
11	Correct	103 ms	5092 KB	Output is correct
12	Correct	72 ms	5220 KB	Output is correct
13	Correct	50 ms	8040 KB	Output is correct
14	Correct	70 ms	8108 KB	Output is correct
15	Correct	387 ms	13472 KB	Output is correct
16	Correct	128 ms	13472 KB	Output is correct
17	Correct	629 ms	15640 KB	Output is correct
18	Correct	715 ms	15640 KB	Output is correct
19	Correct	5371 ms	279020 KB	Output is correct
20	Correct	584 ms	279020 KB	Output is correct
21	Correct	58 ms	279020 KB	Output is correct
22	Correct	103 ms	279020 KB	Output is correct
23	Correct	498 ms	279020 KB	Output is correct
24	Correct	725 ms	279020 KB	Output is correct
25	Correct	3001 ms	279020 KB	Output is correct
26	Correct	7515 ms	279900 KB	Output is correct
27	Correct	6533 ms	279900 KB	Output is correct
28	Correct	59 ms	279900 KB	Output is correct
29	Correct	84 ms	279900 KB	Output is correct
30	Correct	113 ms	279900 KB	Output is correct
31	Correct	109 ms	279900 KB	Output is correct
32	Correct	573 ms	279900 KB	Output is correct
33	Correct	987 ms	279900 KB	Output is correct
34	Correct	3623 ms	279900 KB	Output is correct
35	Correct	6861 ms	279900 KB	Output is correct
36	Correct	91 ms	279900 KB	Output is correct
37	Correct	556 ms	279900 KB	Output is correct
38	Correct	7164 ms	279900 KB	Output is correct
39	Correct	8042 ms	279900 KB	Output is correct
40	Correct	7087 ms	279900 KB	Output is correct
41	Correct	7898 ms	279900 KB	Output is correct
42	Correct	6620 ms	279900 KB	Output is correct
43	Correct	604 ms	279900 KB	Output is correct
44	Correct	5829 ms	282256 KB	Output is correct
45	Correct	674 ms	282256 KB	Output is correct
46	Correct	6932 ms	286664 KB	Output is correct
47	Correct	74 ms	286664 KB	Output is correct
48	Correct	100 ms	286664 KB	Output is correct
49	Correct	572 ms	286664 KB	Output is correct
50	Correct	1268 ms	286664 KB	Output is correct
51	Correct	1069 ms	286664 KB	Output is correct
52	Correct	2759 ms	286664 KB	Output is correct
53	Correct	2338 ms	286664 KB	Output is correct
54	Correct	4247 ms	286664 KB	Output is correct
55	Correct	3791 ms	286664 KB	Output is correct
56	Correct	4973 ms	286664 KB	Output is correct
57	Correct	6356 ms	286664 KB	Output is correct
58	Correct	6879 ms	286664 KB	Output is correct
59	Correct	6416 ms	287872 KB	Output is correct
60	Correct	7797 ms	287872 KB	Output is correct

답안 #67619

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