Submission #299090

#	Time	Username	Problem	Language	Result	Execution time	Memory
299090		square1001	Building Skyscrapers (CEOI19_skyscrapers)	C++14	22 / 100	3571 ms	4508 KiB

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 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 12
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19