oj.uz

Submission #299090

# Submission time Handle Problem Language Result Execution time Memory
299090 2020-09-14T13:18:29 Z square1001 Building Skyscrapers (CEOI19_skyscrapers) C++14
22 / 100
 3500 ms 4508 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Execution timed out 3571 ms 4508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory 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 -