제출 #1194923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194923		irmuun	Building Skyscrapers (CEOI19_skyscrapers)	C++20	0 / 100	3591 ms	33404 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=15e4+5;

int n,t,cnt;
int x[N],y[N];
bool vis[N],ok[N];
vector<int>g[N];
map<pair<int,int>,int>mp;
vector<int>dx={-1,0,1,0,-1,-1,1,1};
vector<int>dy={0,-1,0,1,-1,1,-1,1};

void dfs(int x){
	vis[x]=true;
	cnt++;
	for(int y:g[x]){
		if(!vis[y]){
			dfs(y);
		}
	}
}
void solve(int x){
	vis[x]=true;
	cnt++;
	for(int y:g[x]){
		if(ok[y]&&!vis[y]){
			solve(y);
			if(!ok[x]){
				return;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		mp[{x[i],y[i]}]=i;
	}
	if(t==1){
		for(int i=1;i<=n;i++){
			for(int j=0;j<8;j++){
				int nx=x[i]+dx[j],ny=y[i]+dy[j];
				if(int f=mp[{nx,ny}];f>0){
					g[i].pb(f);
				}
			}
		}
		fill(vis,vis+n+1,false);
		cnt=0;
		dfs(1);
		if(cnt<n){
			cout<<"NO";
			return 0;
		}
		vector<int>ans;
		fill(ok,ok+n+1,true);
		while(ans.size()<n){
			int pos=-1;
			for(int i=1;i<=n;i++){
				if(ok[i]){
					ok[i]=false;
					cnt=0;
					fill(vis,vis+n+1,false);
					solve(i);
					if(cnt==n-ans.size()){
						pos=i;
						break;
					}
					ok[i]=true;
				}
			}
			if(pos==-1) break;
			ans.pb(pos);
			ok[pos]=false;
		}
		if(ans.size()==n){
			cout<<"YES\n";
			for(int i:ans){
				cout<<i<<"\n";
			}
		}
		else{
			cout<<"NO";
		}
	}
	else{
		for(int i=1;i<=n;i++){
			for(int j=0;j<8;j++){
				int nx=x[i]+dx[j],ny=y[i]+dy[j];
				if(int f=mp[{nx,ny}];f>0){
					g[i].pb(f);
				}
			}
		}
		cnt=0;
		fill(vis,vis+n+1,false);
		dfs(1);
		if(cnt<n){
			cout<<"NO";
			return 0;
		}
		vector<int>ans;
		fill(ok,ok+n+1,true);
		while(ans.size()<n){
			int pos=-1;
			for(int i=n;i>=1;i--){
				if(ok[i]){
					ok[i]=false;
					cnt=0;
					fill(vis,vis+n+1,false);
					solve(i);
					if(cnt==n-ans.size()){
						pos=i;
						break;
					}
					ok[i]=true;
				}
			}
			if(pos==-1) break;
			ans.pb(pos);
			ok[pos]=false;
		}
		if(ans.size()==n){
			cout<<"YES\n";
			for(int i:ans){
				cout<<i<<"\n";
			}
		}
		else{
			cout<<"NO";
		}
	}
}

• 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