oj.uz

Submission #396354

# Submission time Handle Problem Language Result Execution time Memory
396354 2021-04-29T20:08:25 Z 4fecta Road Construction (JOI21_road_construction) C++17
18 / 100
 1229 ms 56088 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 250005;

int n, k;
pii a[MN];

int cost(pii p, pii q) {
    return abs(p.f - q.f) + abs(p.s - q.s);
}

bool cmp(pii p, pii q) {
    return cost(a[p.f], a[p.s]) > cost(a[q.f], a[q.s]);
}

int32_t main() {
    boost();

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].f >> a[i].s;
    if (n <= 1000) {
        vector<int> v;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                v.push_back(cost(a[i], a[j]));
            }
        }
        sort(v.begin(), v.end());
        for (int i = 1; i <= k; i++) printf("%lld\n", v[i - 1]);
        return 0;
    }
    sort(a + 1, a + n + 1);
    priority_queue<pii, vector<pii>, decltype(&cmp)> q(cmp);
    set<pii> vis;
    for (int i = 2; i <= n; i++) q.push({i - 1, i}), vis.insert({i - 1, i});
    while (q.size() && k--) {
        pii i = q.top(); q.pop();
        printf("%lld\n", cost(a[i.f], a[i.s]));
        if (i.s < n && !vis.count({i.f, i.s + 1})) q.push({i.f, i.s + 1}), vis.insert({i.f, i.s + 1});
        if (i.f > 1 && !vis.count({i.f - 1, i.s})) q.push({i.f - 1, i.s}), vis.insert({i.f - 1, i.s});
    }


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6960 KB Output is correct
2 Correct 81 ms 6968 KB Output is correct
3 Correct 56 ms 5052 KB Output is correct
4 Correct 73 ms 5032 KB Output is correct
5 Correct 79 ms 5824 KB Output is correct
6 Correct 26 ms 4556 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 52152 KB Output is correct
2 Correct 1186 ms 52128 KB Output is correct
3 Correct 55 ms 4864 KB Output is correct
4 Correct 559 ms 43512 KB Output is correct
5 Correct 377 ms 43688 KB Output is correct
6 Correct 375 ms 43616 KB Output is correct
7 Correct 474 ms 56088 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 28852 KB Output is correct
2 Correct 169 ms 28852 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 139 ms 26656 KB Output is correct
5 Correct 161 ms 29020 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 28852 KB Output is correct
2 Correct 169 ms 28852 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 139 ms 26656 KB Output is correct
5 Correct 161 ms 29020 KB Output is correct
6 Incorrect 167 ms 28864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6960 KB Output is correct
2 Correct 81 ms 6968 KB Output is correct
3 Correct 56 ms 5052 KB Output is correct
4 Correct 73 ms 5032 KB Output is correct
5 Correct 79 ms 5824 KB Output is correct
6 Correct 26 ms 4556 KB Output is correct
7 Incorrect 614 ms 39500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6960 KB Output is correct
2 Correct 81 ms 6968 KB Output is correct
3 Correct 56 ms 5052 KB Output is correct
4 Correct 73 ms 5032 KB Output is correct
5 Correct 79 ms 5824 KB Output is correct
6 Correct 26 ms 4556 KB Output is correct
7 Correct 1229 ms 52152 KB Output is correct
8 Correct 1186 ms 52128 KB Output is correct
9 Correct 55 ms 4864 KB Output is correct
10 Correct 559 ms 43512 KB Output is correct
11 Correct 377 ms 43688 KB Output is correct
12 Correct 375 ms 43616 KB Output is correct
13 Correct 474 ms 56088 KB Output is correct
14 Correct 167 ms 28852 KB Output is correct
15 Correct 169 ms 28852 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 139 ms 26656 KB Output is correct
18 Correct 161 ms 29020 KB Output is correct
19 Incorrect 167 ms 28864 KB Output isn't correct
20 Halted 0 ms 0 KB -