Submission #519133

#	Time	Username	Problem	Language	Result	Execution time	Memory
519133		fallingstar	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	2 ms	3824 KiB

skyscrapers

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

map<pair<int, int>, int> mp;

const int N = 1.5e5 + 2;

vector<int> g[N];
int deg[N];
vector<int> ord;

void dfs(int u)
{
    deg[u] = 0;
    ord.push_back(u);
    int cand = -1;
    for (int v : g[u])
        if (deg[v] > 0 && (cand == -1 || deg[v] < deg[cand]))
            cand = v;
    if (cand != -1) {
        for (int v : g[u])
            if (deg[v] > 0) --deg[v];
        dfs(cand);
    }
}

int main()
{
    int n; cin >> n;
    int subtask; cin >> subtask;
    if (subtask == 2) return 1;
    for (int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;

        for (int dir = 0; dir < 8; ++dir) {
            int u = x + dx[dir], v = y + dy[dir];
            if (auto it = mp.find({u, v}); it != mp.end()) {
                int j = it->second;
                g[i].push_back(j);
                g[j].push_back(i);
                ++deg[i], ++deg[j];
            }
        }

        mp[{x, y}] = i;
    }

    int st = 0;
    for (int i = 1; i < n; ++i)
        if (g[i].size() < g[st].size()) st = i;

    dfs(st);
    for (int i = 0; i < n; ++i)
        if (deg[i] > 0) {
            cout << "NO";
            return 0;
        }
    reverse(ord.begin(), ord.end());
    cout << "YES\n";
    for (int u : ord) cout << u + 1 << '\n';
    return 0;
}

• 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