답안 #299090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299090	2020-09-14T13:18:29 Z	square1001	Building Skyscrapers (CEOI19_skyscrapers)	C++14	22 / 100	3500 ms	4508 KB

skyscrapers

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const vector<int> dxa = { 0, 1, 0, -1 };
const vector<int> dya = { 1, 0, -1, 0 };
class disjoint_set {
private:
	int N;
	vector<int> par;
public:
	disjoint_set() : N(0), par() {};
	disjoint_set(int N_) : N(N_), par(N_) {
		for(int i = 0; i < N_; ++i) {
			par[i] = i;
		}
	}
	int root(int x) {
		if(par[x] == x) return x;
		return par[x] = root(par[x]);
	}
	void link(int x, int y) {
		par[root(x)] = root(y);
	}
	bool connected(int x, int y) {
		return root(x) == root(y);
	}
};
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, T;
	cin >> N >> T;
	vector<int> X(N), Y(N);
	for(int i = 0; i < N; ++i) {
		cin >> X[i] >> Y[i];
	}
	int xl = *min_element(X.begin(), X.end());
	int yl = *min_element(Y.begin(), Y.end());
	for(int i = 0; i < N; ++i) {
		X[i] -= xl - 1;
		Y[i] -= yl - 1;
	}
	int H = *max_element(X.begin(), X.end()) + 2;
	int W = *max_element(Y.begin(), Y.end()) + 2;
	vector<vector<int> > G(N);
	for(int i = 0; i < N; ++i) {
		for(int j = i + 1; j < N; ++j) {
			int d = max(abs(X[i] - X[j]), abs(Y[i] - Y[j]));
			if(d == 1) {
				G[i].push_back(j);
				G[j].push_back(i);
			}
		}
	}
	vector<bool> vis_ini(N);
	function<void(int)> dfs_ini = [&](int pos) {
		vis_ini[pos] = true;
		for(int i : G[pos]) {
			if(!vis_ini[i]) {
				dfs_ini(i);
			}
		}
	};
	dfs_ini(0);
	if(vis_ini != vector<bool>(N, true)) {
		cout << "NO" << endl;
	}
	else {
		vector<vector<bool> > building(H, vector<bool>(W, false));
		for(int i = 0; i < N; ++i) {
			building[X[i]][Y[i]] = true;
		}
		disjoint_set uf(H * W);
		for(int i = 0; i < H; ++i) {
			for(int j = 0; j < W; ++j) {
				if(building[i][j]) continue;
				for(int k = 0; k < 4; ++k) {
					int tx = i + dxa[k], ty = j + dya[k];
					if(0 <= tx && tx < H && 0 <= ty && ty < W && !building[tx][ty]) {
						uf.link(i * W + j, tx * W + ty);
					}
				}
			}
		}
		vector<bool> used(N, false);
		vector<int> seq;
		for(int i = 0; i < N; ++i) {
			vector<bool> vis(N);
			function<void(int)> dfs = [&](int pos) {
				vis[pos] = true;
				for(int j : G[pos]) {
					if(!vis[j] && !used[j]) {
						dfs(j);
					}
				}
			};
			for(int j = 0; j < N; ++j) {
				if(used[j]) continue;
				used[j] = true;
				int comps = 0;
				vis = vector<bool>(N, false);
				for(int k = 0; k < N; ++k) {
					if(!used[k] && !vis[k]) {
						dfs(k);
						++comps;
					}
				}
				bool ok = false;
				for(int k = 0; k < 4; ++k) {
					int tx = X[j] + dxa[k], ty = Y[j] + dya[k];
					if(uf.connected(0, tx * W + ty)) ok = true;
				}
				if(comps <= 1 && ok) {
					seq.push_back(j);
					for(int k = 0; k < 4; ++k) {
						int tx = X[j] + dxa[k], ty = Y[j] + dya[k];
						if(!building[tx][ty]) {
							uf.link(X[j] * W + Y[j], tx * W + ty);
						}
					}
					building[X[j]][Y[j]] = false;
					break;
				}
				used[j] = false;
			}
		}
		reverse(seq.begin(), seq.end());
		cout << "YES" << '\n';
		for(int i = 0; i < N; ++i) {
			cout << seq[i] + 1 << '\n';
		}
	}
	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	ans=YES N=1
2	Correct	0 ms	384 KB	ans=YES N=4
3	Correct	0 ms	384 KB	ans=NO N=4
4	Correct	0 ms	384 KB	ans=YES N=5
5	Correct	0 ms	384 KB	ans=YES N=9
6	Correct	0 ms	384 KB	ans=YES N=5
7	Correct	0 ms	384 KB	ans=NO N=9
8	Correct	0 ms	384 KB	ans=NO N=10
9	Correct	0 ms	384 KB	ans=YES N=10
10	Correct	0 ms	384 KB	ans=YES N=10
11	Correct	0 ms	384 KB	ans=YES N=10
12	Correct	0 ms	384 KB	ans=YES N=9
13	Correct	0 ms	384 KB	ans=YES N=9
14	Correct	0 ms	384 KB	ans=YES N=8
15	Correct	0 ms	384 KB	ans=YES N=8
16	Correct	0 ms	384 KB	ans=NO N=2

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	ans=YES N=1
2	Correct	0 ms	384 KB	ans=YES N=4
3	Correct	0 ms	384 KB	ans=NO N=4
4	Correct	0 ms	384 KB	ans=YES N=5
5	Correct	0 ms	384 KB	ans=YES N=9
6	Correct	0 ms	384 KB	ans=YES N=5
7	Correct	0 ms	384 KB	ans=NO N=9
8	Correct	0 ms	384 KB	ans=NO N=10
9	Correct	0 ms	384 KB	ans=YES N=10
10	Correct	0 ms	384 KB	ans=YES N=10
11	Correct	0 ms	384 KB	ans=YES N=10
12	Correct	0 ms	384 KB	ans=YES N=9
13	Correct	0 ms	384 KB	ans=YES N=9
14	Correct	0 ms	384 KB	ans=YES N=8
15	Correct	0 ms	384 KB	ans=YES N=8
16	Correct	0 ms	384 KB	ans=NO N=2
17	Correct	0 ms	384 KB	ans=YES N=17
18	Correct	1 ms	288 KB	ans=YES N=25
19	Correct	2 ms	384 KB	ans=YES N=100
20	Correct	10 ms	384 KB	ans=YES N=185
21	Correct	1 ms	384 KB	ans=NO N=174
22	Correct	2 ms	384 KB	ans=YES N=90
23	Correct	1 ms	384 KB	ans=YES N=63
24	Correct	2 ms	384 KB	ans=YES N=87
25	Correct	11 ms	384 KB	ans=YES N=183
26	Correct	10 ms	384 KB	ans=YES N=188
27	Correct	9 ms	384 KB	ans=YES N=183
28	Correct	11 ms	384 KB	ans=YES N=189
29	Correct	12 ms	512 KB	ans=YES N=200
30	Correct	13 ms	384 KB	ans=YES N=190
31	Correct	14 ms	384 KB	ans=YES N=187
32	Correct	9 ms	384 KB	ans=YES N=187
33	Correct	15 ms	384 KB	ans=YES N=182
34	Correct	13 ms	384 KB	ans=YES N=184
35	Correct	20 ms	384 KB	ans=YES N=188
36	Correct	13 ms	384 KB	ans=YES N=181
37	Correct	17 ms	384 KB	ans=YES N=188
38	Correct	22 ms	384 KB	ans=YES N=191
39	Correct	16 ms	384 KB	ans=YES N=196
40	Correct	17 ms	384 KB	ans=YES N=196
41	Correct	17 ms	384 KB	ans=YES N=196
42	Correct	16 ms	384 KB	ans=YES N=196
43	Correct	17 ms	384 KB	ans=YES N=195

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	ans=YES N=1
2	Correct	0 ms	384 KB	ans=YES N=4
3	Correct	0 ms	384 KB	ans=NO N=4
4	Correct	0 ms	384 KB	ans=YES N=5
5	Correct	0 ms	384 KB	ans=YES N=9
6	Correct	0 ms	384 KB	ans=YES N=5
7	Correct	0 ms	384 KB	ans=NO N=9
8	Correct	0 ms	384 KB	ans=NO N=10
9	Correct	0 ms	384 KB	ans=YES N=10
10	Correct	0 ms	384 KB	ans=YES N=10
11	Correct	0 ms	384 KB	ans=YES N=10
12	Correct	0 ms	384 KB	ans=YES N=9
13	Correct	0 ms	384 KB	ans=YES N=9
14	Correct	0 ms	384 KB	ans=YES N=8
15	Correct	0 ms	384 KB	ans=YES N=8
16	Correct	0 ms	384 KB	ans=NO N=2
17	Correct	0 ms	384 KB	ans=YES N=17
18	Correct	1 ms	288 KB	ans=YES N=25
19	Correct	2 ms	384 KB	ans=YES N=100
20	Correct	10 ms	384 KB	ans=YES N=185
21	Correct	1 ms	384 KB	ans=NO N=174
22	Correct	2 ms	384 KB	ans=YES N=90
23	Correct	1 ms	384 KB	ans=YES N=63
24	Correct	2 ms	384 KB	ans=YES N=87
25	Correct	11 ms	384 KB	ans=YES N=183
26	Correct	10 ms	384 KB	ans=YES N=188
27	Correct	9 ms	384 KB	ans=YES N=183
28	Correct	11 ms	384 KB	ans=YES N=189
29	Correct	12 ms	512 KB	ans=YES N=200
30	Correct	13 ms	384 KB	ans=YES N=190
31	Correct	14 ms	384 KB	ans=YES N=187
32	Correct	9 ms	384 KB	ans=YES N=187
33	Correct	15 ms	384 KB	ans=YES N=182
34	Correct	13 ms	384 KB	ans=YES N=184
35	Correct	20 ms	384 KB	ans=YES N=188
36	Correct	13 ms	384 KB	ans=YES N=181
37	Correct	17 ms	384 KB	ans=YES N=188
38	Correct	22 ms	384 KB	ans=YES N=191
39	Correct	16 ms	384 KB	ans=YES N=196
40	Correct	17 ms	384 KB	ans=YES N=196
41	Correct	17 ms	384 KB	ans=YES N=196
42	Correct	16 ms	384 KB	ans=YES N=196
43	Correct	17 ms	384 KB	ans=YES N=195
44	Correct	8 ms	384 KB	ans=NO N=1934
45	Correct	8 ms	640 KB	ans=NO N=1965
46	Execution timed out	3517 ms	640 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	384 KB	ans=NO N=1934
2	Correct	8 ms	512 KB	ans=NO N=1965
3	Execution timed out	3565 ms	640 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	ans=YES N=1
2	Correct	0 ms	384 KB	ans=YES N=4
3	Correct	0 ms	384 KB	ans=NO N=4
4	Correct	0 ms	384 KB	ans=YES N=5
5	Correct	0 ms	384 KB	ans=YES N=9
6	Correct	0 ms	384 KB	ans=YES N=5
7	Correct	0 ms	384 KB	ans=NO N=9
8	Correct	0 ms	384 KB	ans=NO N=10
9	Correct	0 ms	384 KB	ans=YES N=10
10	Correct	0 ms	384 KB	ans=YES N=10
11	Correct	0 ms	384 KB	ans=YES N=10
12	Correct	0 ms	384 KB	ans=YES N=9
13	Correct	0 ms	384 KB	ans=YES N=9
14	Correct	0 ms	384 KB	ans=YES N=8
15	Correct	0 ms	384 KB	ans=YES N=8
16	Correct	0 ms	384 KB	ans=NO N=2
17	Correct	0 ms	384 KB	ans=YES N=17
18	Correct	1 ms	288 KB	ans=YES N=25
19	Correct	2 ms	384 KB	ans=YES N=100
20	Correct	10 ms	384 KB	ans=YES N=185
21	Correct	1 ms	384 KB	ans=NO N=174
22	Correct	2 ms	384 KB	ans=YES N=90
23	Correct	1 ms	384 KB	ans=YES N=63
24	Correct	2 ms	384 KB	ans=YES N=87
25	Correct	11 ms	384 KB	ans=YES N=183
26	Correct	10 ms	384 KB	ans=YES N=188
27	Correct	9 ms	384 KB	ans=YES N=183
28	Correct	11 ms	384 KB	ans=YES N=189
29	Correct	12 ms	512 KB	ans=YES N=200
30	Correct	13 ms	384 KB	ans=YES N=190
31	Correct	14 ms	384 KB	ans=YES N=187
32	Correct	9 ms	384 KB	ans=YES N=187
33	Correct	15 ms	384 KB	ans=YES N=182
34	Correct	13 ms	384 KB	ans=YES N=184
35	Correct	20 ms	384 KB	ans=YES N=188
36	Correct	13 ms	384 KB	ans=YES N=181
37	Correct	17 ms	384 KB	ans=YES N=188
38	Correct	22 ms	384 KB	ans=YES N=191
39	Correct	16 ms	384 KB	ans=YES N=196
40	Correct	17 ms	384 KB	ans=YES N=196
41	Correct	17 ms	384 KB	ans=YES N=196
42	Correct	16 ms	384 KB	ans=YES N=196
43	Correct	17 ms	384 KB	ans=YES N=195
44	Correct	8 ms	384 KB	ans=NO N=1934
45	Correct	8 ms	640 KB	ans=NO N=1965
46	Execution timed out	3517 ms	640 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3571 ms	4508 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	384 KB	ans=NO N=1934
2	Correct	8 ms	512 KB	ans=NO N=1965
3	Execution timed out	3565 ms	640 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

답안 #299090

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 0 / 12.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #6 0 / 10.0

Subtask #7 0 / 19.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
0 / 12.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0

Subtask #6
0 / 10.0

Subtask #7
0 / 19.0