Submission #703098

#	Time	Username	Problem	Language	Result	Execution time	Memory
703098		Cyanmond	Building Skyscrapers (CEOI19_skyscrapers)	C++17	8 / 100	184 ms	8428 KiB

skyscrapers

#include <bits/stdc++.h>

struct Point {
    int r, c;
};
auto compPoint = [](Point a, Point b) {
    return std::make_pair(a.r, a.c) < std::make_pair(b.r, b.c);
};

std::pair<int, int> dxy[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

int main() {
    int N, T;
    std::cin >> N >> T;
    std::vector<Point> sks(N);
    for (auto &[r, c] : sks) {
        std::cin >> r >> c;
    }
    std::map<Point, int, decltype(compPoint)> skMap(compPoint);
    for (int i = 0; i < N; ++i) {
        skMap[sks[i]] = i;
    }

    std::vector<int> dist(N, -1);
    dist[0] = 0;
    std::queue<int> que;
    que.push(0);
    while (not que.empty()) {
        const auto f = que.front();
        que.pop();
        const auto &[r, c] = sks[f];
        for (const auto &[ar, ac] : dxy) {
            const int nr = r + ar, nc = c + ac;
            auto itr = skMap.find({nr, nc});
            if (itr == skMap.end()) {
                continue;
            }
            const int t = itr->second;
            if (dist[t] != -1) {
                continue;
            }
            dist[t] = dist[f] + 1;
            que.push(t);
        }
    }

    if (std::any_of(dist.begin(), dist.end(), [&](int x) {
        return x == -1;
    })) {
        std::cout << "NO" << std::endl;
        return 0;
    }
    std::cout << "YES" << std::endl;
    std::vector<std::vector<int>> distList(N);
    for (int i = 0; i < N; ++i) {
        distList[dist[i]].push_back(i);
    }
    for (const auto &vec : distList) {
        for (const auto e : vec) {
            std::cout << e + 1 << std::endl;
        }
    }
}

• 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