oj.uz

Submission #1079632

# Submission time Handle Problem Language Result Execution time Memory
1079632 2024-08-28T19:20:55 Z emuyumi Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 119512 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 46164 KB Output is correct
2 Correct 271 ms 46160 KB Output is correct
3 Correct 130 ms 24656 KB Output is correct
4 Correct 133 ms 24660 KB Output is correct
5 Correct 245 ms 45136 KB Output is correct
6 Correct 5 ms 1368 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3077 ms 63536 KB Output is correct
2 Correct 3134 ms 63496 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 10093 ms 60728 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3077 ms 63536 KB Output is correct
2 Correct 3134 ms 63496 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 10093 ms 60728 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 46164 KB Output is correct
2 Correct 271 ms 46160 KB Output is correct
3 Correct 130 ms 24656 KB Output is correct
4 Correct 133 ms 24660 KB Output is correct
5 Correct 245 ms 45136 KB Output is correct
6 Correct 5 ms 1368 KB Output is correct
7 Correct 3633 ms 119432 KB Output is correct
8 Correct 3635 ms 119512 KB Output is correct
9 Correct 136 ms 24656 KB Output is correct
10 Correct 3124 ms 115612 KB Output is correct
11 Correct 1697 ms 114984 KB Output is correct
12 Correct 1559 ms 112788 KB Output is correct
13 Correct 1450 ms 104172 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 46164 KB Output is correct
2 Correct 271 ms 46160 KB Output is correct
3 Correct 130 ms 24656 KB Output is correct
4 Correct 133 ms 24660 KB Output is correct
5 Correct 245 ms 45136 KB Output is correct
6 Correct 5 ms 1368 KB Output is correct
7 Execution timed out 10044 ms 84464 KB Time limit exceeded
8 Halted 0 ms 0 KB -