oj.uz

Submission #1079630

# Submission time Handle Problem Language Result Execution time Memory
1079630 2024-08-28T19:17:28 Z emuyumi Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 81732 KB 
#include <bits/stdc++.h>

using namespace std;

int 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;
            // cerr  << b << '\n';
            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();
                // cerr << i << " " << j << " " << b << " " << pts[i].size() << '\n';
            }
            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) {
                // cerr << "! " << pts[i][j] << '\n';
                relax({i, j, pts[i][j], 0});
            }
            // cerr << '\n';
        }
        // cerr << " AAAA " << " " << pq.size() << '\n';
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 40416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 81732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3195 ms 58716 KB Output is correct
2 Correct 3254 ms 56788 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3195 ms 58716 KB Output is correct
2 Correct 3254 ms 56788 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 40416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 40416 KB Output isn't correct
2 Halted 0 ms 0 KB -