oj.uz

Submission #299060

# Submission time Handle Problem Language Result Execution time Memory
299060 2020-09-14T12:52:37 Z square1001 Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 3500 ms 495528 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<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<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<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(0 <= tx && tx < H && 0 <= ty && ty < W && building[tx][ty]) {
							uf.link(i * W + j, tx * W + ty);
						}
					}
					break;
				}
				used[j] = false;
				building[X[j]][Y[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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ans=YES N=1
2 Correct 1 ms 384 KB ans=YES N=4
3 Correct 1 ms 384 KB ans=NO N=4
4 Correct 1 ms 384 KB ans=YES N=5
5 Runtime error 1 ms 512 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ans=YES N=1
2 Correct 1 ms 384 KB ans=YES N=4
3 Correct 1 ms 384 KB ans=NO N=4
4 Correct 1 ms 384 KB ans=YES N=5
5 Runtime error 1 ms 512 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ans=YES N=1
2 Correct 1 ms 384 KB ans=YES N=4
3 Correct 1 ms 384 KB ans=NO N=4
4 Correct 1 ms 384 KB ans=YES N=5
5 Runtime error 1 ms 512 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 469 ms 495528 KB Execution killed with signal 11
2 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 1 ms 384 KB ans=YES N=4
3 Correct 1 ms 384 KB ans=NO N=4
4 Correct 1 ms 384 KB ans=YES N=5
5 Runtime error 1 ms 512 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 469 ms 495528 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -