Submission #447183

#	Time	Username	Problem	Language	Result	Execution time	Memory
447183		8e7	Building Skyscrapers (CEOI19_skyscrapers)	C++17	51 / 100	3558 ms	24032 KiB

skyscrapers

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 150005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
unordered_map<ll, int> mp;
unordered_set<ll> bfs, cand;
ll h(pii p) {
	return (((ll)p.ff)<<30) + p.ss;
}
pii pos[maxn];
bool vis[maxn], out[maxn], art[maxn], used[maxn];
vector<int> adj[maxn];
void dfs(int n) {
	int x = pos[n].ff, y = pos[n].ss;
	vis[n] = 1;
	for (int dx = -1;dx <= 1;dx++) {
		for (int dy = -1;dy <= 1;dy++) {
			pii to = {x + dx, y + dy};
			cand.insert(h(to));
			if (dx == 0 && dy == 0) continue;
			int v = mp[h(to)];
			if (v) {
				if (!vis[v]) dfs(v);
				adj[n].push_back(v);
			}
		}
	}
}
int ans[maxn], low[maxn], ti[maxn];
int c = 0;
void dfs2(int n, int par, int root) {
	vis[n] = 1;
	low[n] = ti[n] = c++;
	int p = ti[n], chi = 0, val = 0;
	for (int v:adj[n]) {
		if (used[v]) continue;
		if (!vis[v]) {
			chi++;
			dfs2(v, n, root);
			low[n] = min(low[n], low[v]);
			val = max(val, low[v]);
		} else if (v != par) {
			p = min(p, ti[v]);
		}
	}
	if ((n != root && chi && val >= ti[n]) || (n == root && chi > 1)) art[n] = 1;
	low[n] = min(low[n], p);
}
int main() {
	io
	int n, type;
	cin >> n >> type;
	int mx = 1<<30, my = 1<<30, st = 0;
	for (int i = 1;i <= n;i++) {
		cin >> pos[i].ff >> pos[i].ss;
		mx = min(mx, pos[i].ff);
		if (pos[i].ss < my) {
			my = pos[i].ss;
			st = pos[i].ff;
		}
	}
	for (int i = 1;i <= n;i++) {
		pos[i] = {pos[i].ff - mx + 1, pos[i].ss - my + 1};
		mp[h(pos[i])] = i;
	}
	dfs(1);
	for (int i = 1;i <= n;i++) {
		if (!vis[i]) {
			cout << "NO" << endl;
			return 0;
		}
		vis[i] = 0;
	}
	queue<pii> que;
	que.push({st - mx + 1, 0});
	bfs.insert(h(que.front()));
	for (int it = 0;it < n;it++) {
		while (que.size()) {
			pii cur = que.front();que.pop();
			for (int k = 0;k < 4;k++) {
				pii ne = {cur.ff + dir[k][0], cur.ss + dir[k][1]};
				ll x = h(ne);
				if (ne.ff >= 0 && ne.ss >= 0) {
					int v = mp[x];
					if (v) out[v] = 1;
					else {
						if (cand.find(x) != cand.end() && bfs.find(x) == bfs.end()) {
							bfs.insert(x);
							que.push(ne);
						}	
					}
				}
			}
		}
		for (int j = n;j >= 1;j--) art[j] = 0, vis[j] = 0, low[j] = ti[j] = 0;	
		c = 0;
		for (int j = n;j >= 1;j--) {
			if (!used[j]) {
				dfs2(j, 0, j);
				break;
			}
		}	
		//pary(art + 1, art + n + 1);
		for (int j = n;j >= 1;j--) {
			if (!used[j] && !art[j] && out[j]) {
				ans[it] = j;
				//cout << j<< endl;
				que.push(pos[j]);
				bfs.insert(h(pos[j]));
				used[j] = 1;
				break;
			}
		}
	}
	cout << "YES" << endl;
	for (int i = n - 1;i >= 0;i--) cout << ans[i] << "\n";
}
/*
 
3
2
0 0
0 1
0 2
 
9
1
-5 -5
-4 -6
-3 -7
-2 -6
-1 -5
-2 -4
-3 -3
-4 -4
-3 -5
 
7 1
0 4
0 5
0 3
0 2
0 7
0 1
0 6
*/

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19