Submission #1220585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220585		Trumling	Building Skyscrapers (CEOI19_skyscrapers)	C++20	0 / 100	1923 ms	9344 KiB

skyscrapers

//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
vector<vector<ll>>g;
pair<ll,ll>arr[150001];
vector<bool>vis;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin>>n;

ll t;
cin>>t;
g.assign(n+1,vector<ll>());
vis.assign(n+1,0);
long double sumx=0,sumy=0;

for(int i=0;i<n;i++)
{
    cin>>arr[i].F>>arr[i].S;
    sumx+=arr[i].F;
    sumy+=arr[i].S;
}
sumx/=n;
sumy/=n;

ll start=0;
for(int i=0;i<n;i++)
    if(abs(arr[i].F-sumx) + abs(arr[i].S - sumy) < abs(arr[start].F-sumx) + abs(arr[start].S - sumy))
        start=i;

for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
    {
        ll dx=abs(arr[i].F-arr[j].F);
        ll dy=abs(arr[i].S-arr[j].S);
        if(dx<=1 && dy<=1)
            {
                g[i+1].pb(j+1);
                g[j+1].pb(i+1);
            }
    }

vector<bool>vis(n+1,0);
vis[start+1]=1;
priority_queue<pair<ll,ll>>q;
queue<ll>ans;
  
q.push({0,start+1});
bool rev=0;
while(!q.empty())
{
    ll curr=q.top().F;
    ans.push(curr);
    q.pop();

    for(auto x:g[curr])
        if(!vis[x])
        {
            vis[x]=1;
            q.push({-(abs(arr[x-1].F-arr[start].F) + abs(arr[x-1].S-arr[start].S)),x});
        }
}

bool tf=1;
for(int i=1;i<=n;i++)
    if(!vis[i])
        {
            tf=0;
            break;
        }
if(!tf)
{
    cout<<"NO";
    return 0;
}
cout<<"YES"<<'\n';
while(!ans.empty())
{
    cout<<ans.front()<<'\n';
    ans.pop();
}

}

• 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