Submission #924729

#	Time	Username	Problem	Language	Result	Execution time	Memory
924729		Camillus	Building Skyscrapers (CEOI19_skyscrapers)	C++17	54 / 100	576 ms	16668 KiB

skyscrapers

/// @author Camillus
#include "bits/stdc++.h"

using ll = long long;
using namespace std;

struct dsu {
    vector<int> p;

    dsu() = default;
    dsu(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int get(int x) {
        if (x == p[x]) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    void join(int x, int y) {
        x = get(x);
        y = get(y);
        p[x] = y;
    }
};

auto sideN(int x, int y) {
    array<pair<int, int>, 4> result;
    result[0] = pair(x, y - 1);
    result[1] = pair(x, y + 1);
    result[2] = pair(x - 1, y);
    result[3] = pair(x + 1, y);
    return result;
}

auto sideN(const pair<int, int> &pos) {
    return sideN(pos.first, pos.second);
}

auto cornerN(int x, int y) {
    array<pair<int, int>, 8> result;
    // sides
    result[0] = pair(x, y - 1);
    result[1] = pair(x, y + 1);
    result[2] = pair(x - 1, y);
    result[3] = pair(x + 1, y);
    // corners
    result[4] = pair(x + 1, y + 1);
    result[5] = pair(x + 1, y - 1);
    result[6] = pair(x - 1, y + 1);
    result[7] = pair(x - 1, y - 1);
    return result;
}

auto cornerN(const pair<int, int> &pos) {
    return cornerN(pos.first, pos.second);
}

ll dist(const pair<int, int> &first, const pair<int, int> &second) {
    ll x = first.first - second.first;
    ll y = first.second - second.second;
    return x * x + y * y;
}

mt19937 rnd(228);

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, t;
    cin >> n >> t;

    vector<pair<int, int>> a(n);
    map<pair<int, int>, int> b;

    for (int i = 0; i < n; i++) {
        int r, c;
        cin >> r >> c;

        a[i] = pair(r, c);
        b[pair(r, c)] = i;
    }

    dsu D(n);

    for (auto [pos_u, u] : b) {
        for (auto pos_v : cornerN(pos_u)) {
            if (b.count(pos_v)) {
                int v = b[pos_v];
                D.join(u, v);
            }
        }
    }

    for (int u = 0; u < n; u++) {
        if (D.get(u) != D.get(0)) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";

    vector<int> ans;

    int start = rnd() % n;

    vector<bool> used(n);
    set<pair<int, int>> Q; 
    used[start] = true;
    Q.emplace(0, start);

    while (!Q.empty()) {
        int u = Q.begin()->second;
        ans.push_back(u);
        Q.erase(Q.begin());

        auto pos_u = a[u];

        for (auto pos_v : cornerN(pos_u)) {
            if (b.count(pos_v)) {
                int v = b[pos_v];
                if (!used[v]) {
                    used[v] = true;
                    Q.emplace(dist(pos_v, a[start]), v);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] + 1 << '\n';
    }
    return 0;
}

• 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