Submission #1072963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072963		emptypringlescan	Building Skyscrapers (CEOI19_skyscrapers)	C++17	54 / 100	385 ms	37084 KiB

skyscrapers

#include <bits/stdc++.h>
using namespace std;
int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
vector<pair<pair<int,int>,int> > adj[150005];
int v[150005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,t;
	cin >> n >> t;
	pair<pair<int,int>,int> arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i].first.first >> arr[i].first.second;
		arr[i].second=i;
	}
	set<pair<pair<int,int>,int> > got;
	set<pair<pair<int,int>,int> >::iterator it;
	for(int i=0; i<n; i++){
		for(int j=0; j<8; j++){
			pair<int,int> nx={arr[i].first.first+dx[j],arr[i].first.second+dy[j]};
			it=got.lower_bound({nx,-1});
			if(it==got.end()||it->first!=nx) continue;
			adj[i].push_back(*it);
			adj[it->second].push_back(arr[i]);
		}
		got.insert(arr[i]);
	}
	priority_queue<pair<pair<int,int>,int> > pq;
	pq.push(arr[0]);
	vector<int> ans;
	while(!pq.empty()){
		int y=pq.top().second;
		pq.pop();
		if(v[y]) continue;
		v[y]=1;
		ans.push_back(y);
		for(auto i:adj[y]){
			if(!v[i.second]) pq.push(i);
		}
	}
	if((int)ans.size()!=n){
		cout << "NO";
	}
	else{
		cout << "YES\n";
		for(int i:ans) cout << i+1 << ' ' ;
	}
}

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