Submission #476137

#	Time	Username	Problem	Language	Result	Execution time	Memory
476137		Ozy	Building Skyscrapers (CEOI19_skyscrapers)	C++17	8 / 100	223 ms	16288 KiB

skyscrapers

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 150000

lli n,t,a,b,ini,val,act,k;
map<pair<lli,lli>, lli> mapa;
vector<lli> hijos[MAX+2];
lli dir[16] = {-1,-1,0,1,1,1,0,-1,0,1,1,1,0,-1,-1,-1};
lli visitados[MAX+2];
queue<lli> cola;
vector<lli> res;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> t;

    val = 1000000000000;
    rep(i,1,n) {
        cin >> a >> b;
        if (a < val){
            val = a;
            ini = i;
        }

        mapa[{a,b}] = i;

        rep(o,0,7) {
            if (mapa.find({a+dir[o],b + dir[o+8]}) != mapa.end()) {
                k = mapa[{a+dir[o],b + dir[o+8]}];
                hijos[k].push_back(i);
                hijos[i].push_back(k);
            }
        }
    }
    //correcto

    cola.push(ini);
    visitados[ini] = 1;
    while (!cola.empty()) {

        act = cola.front();
        cola.pop();
        res.push_back(act);

        for(auto h : hijos[act]) {
            if (visitados[h] == 1) continue;
            visitados[h] = 1;
            cola.push(h);
        }
    }

    if (res.size() < n) cout << "NO";
    else {
        cout << "YES\n";
        for (auto r : res) cout << r << "\n";
    }
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:62:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   62 |     if (res.size() < n) cout << "NO";
      |         ~~~~~~~~~~~^~~

• Subtask 1: 8 / 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