Submission #1079632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079632		emuyumi	Road Construction (JOI21_road_construction)	C++17	32 / 100	10093 ms	119512 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, K; cin >> N >> K;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i];
    }
    auto dist = [&](int i, int j) {
        return abs(x[i] - x[j]) + abs(y[i] - y[j]);
    };
    struct Answer {
        int i, j, d;
        bool operator<(const Answer &other) const {
            return tie(d, i, j) < tie(other.d, other.i, other.j);
        }
    };
    set<Answer> ans;
    auto work = [&]() -> void {
        map<int, vector<int>> mp;
        for (int i = 0; i < N; ++i) {
            mp[x[i] + y[i]].push_back(i);
        }
        vector<vector<int>> pts;
        for (auto &[i, v] : mp) {
            sort(v.begin(), v.end(), [&](int i, int j) {
                return y[i] < y[j];
            });
            pts.push_back(v);
        }
        struct Item {
            int i, j, src, d;
            bool operator<(const Item &other) const { return d > other.d; }
        };
        priority_queue<Item> pq;
        auto relax = [&](Item item) -> void {
            auto [i, j, b, d] = item;
            j++;
            while (j == (int)pts[i].size() || x[pts[i][j]] <= x[b]) {
                i++;
                if (i == (int)pts.size()) return;
                j = lower_bound(pts[i].begin(), pts[i].end(), b, [&](int i, int j) {
                    return y[i] < y[j];
                }) - pts[i].begin();
            }
            pq.push({i, j, b, dist(b, pts[i][j])});
        };
        for (int i = 0; i < (int)pts.size(); ++i) {
            for (int j = 0; j < (int)pts[i].size(); ++j) {
                relax({i, j, pts[i][j], 0});
            }
        }
        int T = 0;
        while (!pq.empty() && T <= 2*K) {
            Item best = pq.top(); pq.pop();
            int a = pts[best.i][best.j];
            int b = best.src;
            if (a > b) swap(a, b);
            ans.insert({a, b, best.d});
            relax(best);
            T++;
        }
    };
    for (int d = 0; d < 4; ++d) {
        work();
        for (int i = 0; i < N; ++i) {
            swap(x[i], y[i]);
            x[i] *= -1;
        }
    }
    vector<Answer> vans(ans.begin(), ans.end());
    for (int i = 0; i < K; ++i) {
        cout << vans[i].d << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35