Submission #446285

#	Time	Username	Problem	Language	Result	Execution time	Memory
446285		benedict0724	Building Skyscrapers (CEOI19_skyscrapers)	C++17	54 / 100	721 ms	92476 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

map<pair<int, int>, int> m;
struct node
{
    int x, y, i;
    node() : node(0, 0, 0) {}
    node(int _x, int _y, int _i) : x(_x), y(_y), i(_i) {}
    bool operator < (const node &O) const
    {
        if(x == O.x) return y > O.y;
        return x > O.x;
    }
} Sky[150002];

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};
vector<int> adj[150002];
int X[150002], Y[150002];
bool visited[150002];
queue<int> q;
priority_queue<node> pq;
void bfs(int x)
{
    visited[x] = true;
    pq.push(node(X[x], Y[x], x));
    while(!pq.empty())
    {
        int now = pq.top().i;
        q.push(now);
        pq.pop();
        for(int i : adj[now])
        {
            if(visited[i]) continue;
            visited[i] = true;
            pq.push(node(X[i], Y[i], i));
        }
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, t; cin >> n >> t;
    for(int i=1;i<=n;i++)
    {
        int x, y; cin >> x >> y;
        X[i] = x, Y[i] = y;
        Sky[i] = node(x, y, i);
        m[{x, y}] = i;
        for(int j=0;j<8;j++)
        {
            int tmp = m[{x + dx[j], y+dy[j]}];
            if(tmp == 0) continue;
            adj[tmp].push_back(i);
            adj[i].push_back(tmp);
        }
    }

    sort(Sky + 1, Sky + n + 1);
    bfs(Sky[n].i);

    if(q.size() < n) cout << "NO\n";
    else
    {
        cout << "YES\n";
        while(!q.empty())
        {
            cout << q.front() << "\n";
            q.pop();
        }
    }
}

Compilation message (stderr)

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

• 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