Submission #578865

#	Time	Username	Problem	Language	Result	Execution time	Memory
578865		amunduzbaev	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	1 ms	468 KiB

skyscrapers

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int N = 20;
int r[N], c[N], used[N], is[N][N];
int tin[N], fup[N], ap[N], on[N];
int near[N];
vector<int> edges[N];
int ch[8][2] = {
	{1, 0},
	{0, 1},
	{0, -1},
	{-1, 0},
	{-1, -1},
	{-1, 1},
	{1, -1},
	{1, 1}
};

void dfs(int u){
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x]) continue;
		dfs(x);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, t; cin>>n>>t;
	map<ar<int, 2>, int> mm;
	int r_ = 1e9, c_ = 1e9;
	for(int i=0;i<n;i++){
		cin>>r[i]>>c[i];
		r_ = min(r_, r[i]);
		c_ = min(c_, c[i]);
		for(int t=0;t<8;t++){
			int x = r[i] + ch[t][0], y = c[i] + ch[t][1];
			if(mm.count({x, y})){
				x = mm[{x, y}];
				edges[x].push_back(i);
				edges[i].push_back(x);
			}
		}
		
		mm[{r[i], c[i]}] = i;
	}
	mm.clear();
	for(int i=0;i<n;i++){
		r[i] = r[i] - r_ + (r_ > 0);
		c[i] = c[i] - c_ + (c_ > 0);
		mm[{r[i], c[i]}] = i;
		//~ cout<<r[i]<<" "<<c[i]<<endl;
	}
	
	dfs(0);
	//~ for(int i=0;i<n;i++){
		//~ cout<<used[i]<<" ";
	//~ } cout<<endl;
	for(int i=0;i<n;i++){
		if(!used[i]){
			cout<<"NO\n";
			return 0;
		}
	}
	
	//~ vector<int> mn(n, N);
	int cmp = 1;
	function<void(int, int)> dfs2 = [&](int i, int j){
		is[i][j] = cmp;
		//~ cout<<i<<" "<<j<<endl;
		for(int t=0;t<4;t++){
			int x = i + ch[t][0], y = j + ch[t][1];
			if(mm.count({x, y})){
				if(cmp == 1){
					int k = mm[{x, y}];
					near[k] = 1;
				}
			} else if(~x && x < N && ~y && y < N && !is[x][y]){
				//~ cout<<" -> "<<x<<" "<<y<<endl;
				dfs2(x, y);
			}
		}
	};
	
	for(int i=0;i<N;i++){
		if(!is[i][N-1]) dfs2(i, N - 1);
		if(!is[N-1][i]) dfs2(N - 1, i);
	} cmp++;
	for(int i=N-2;~i;i--){
		for(int j=N-2;~j;j--){
			if(is[i][j] || mm.count({i, j})) continue;
			dfs2(i, j), cmp++;
		}
	}
	
	int tim = 0;
	function<void(int, int)> dfs3 = [&](int u, int p){
		tin[u] = fup[u] = ++tim;
		used[u] = 1;
		int c = 0, cnt = 0;
		for(auto x : edges[u]){
			if(x == p || on[x]) continue;
			if(used[x]){
				fup[u] = min(fup[u], tin[x]);
				c = 1;
			} else {
				cnt++;
				dfs3(x, u);
				fup[u] = min(fup[u], fup[x]);
			}
		}
		
		if(tin[u] > fup[u]){
			ap[u] = 0;
		} else {
			if(c || cnt == 0) ap[u] = 0;
			else if(p == u && cnt == 1) ap[u] = 0;
			else ap[u] = 1;
		}
	};
	//~ cout<<"here"<<endl;
	vector<int> res;
	for(int i=0;i<n;i++){
		memset(used, 0, sizeof used);
		tim = 0;
		for(int i=0;i<n;i++){
			if(on[i]) continue;
			dfs3(i, i); break;
		}
		
		int v = -1;
		for(int i=0;i<n;i++){
			if(ap[i] || on[i]) continue;
			if(near[i]) v = i;
		}
		
		if(v == -1){
			cout<<"NO\n";
			return 0;
		}
		
		on[v] = 1;
		vector<int> tmp;
		for(int t=0;t<4;t++){
			int x = r[v] + ch[t][0], y = c[v] + ch[t][1];
			if(is[x][y] > 1) tmp.push_back(is[x][y]);
		}
		for(int i=0;i<n;i++){
			if(on[i]) continue;
			for(int t=0;t<4;t++){
				int x = r[i] + ch[t][0], y = c[i] + ch[t][1];
				for(auto e : tmp){
					if(is[x][y] == e){
						is[x][y] = 1;
						near[i] = 1;
						break;
					}
				}
			}
		}
		res.push_back(v);
	}
	
	cout<<"YES\n";
	for(auto x : res) cout<<++	x<<" ";
	cout<<"\n";
}

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