oj.uz

Submission #396359

# Submission time Handle Problem Language Result Execution time Memory
396359 2021-04-29T20:19:50 Z 4fecta Road Construction (JOI21_road_construction) C++17
38 / 100
 7512 ms 1580344 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#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 gap = 1; gap <= 75; gap++) {
        for (int i = gap + 1; i <= n; i++) q.push({i - gap, i}), vis.insert({i - gap, 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 85 ms 6960 KB Output is correct
2 Correct 86 ms 6952 KB Output is correct
3 Correct 55 ms 5068 KB Output is correct
4 Correct 56 ms 4988 KB Output is correct
5 Correct 75 ms 5804 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7512 ms 1580228 KB Output is correct
2 Correct 7426 ms 1580344 KB Output is correct
3 Correct 55 ms 4916 KB Output is correct
4 Correct 6640 ms 1580176 KB Output is correct
5 Correct 6803 ms 1580116 KB Output is correct
6 Correct 6731 ms 1580148 KB Output is correct
7 Correct 6740 ms 1580188 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7060 ms 1580064 KB Output is correct
2 Correct 7087 ms 1580056 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 6294 ms 1580076 KB Output is correct
5 Correct 6431 ms 1580064 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7060 ms 1580064 KB Output is correct
2 Correct 7087 ms 1580056 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 6294 ms 1580076 KB Output is correct
5 Correct 6431 ms 1580064 KB Output is correct
6 Correct 7184 ms 1580176 KB Output is correct
7 Correct 7129 ms 1580164 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 7125 ms 1580120 KB Output is correct
11 Correct 6279 ms 1580164 KB Output is correct
12 Correct 6375 ms 1580084 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6960 KB Output is correct
2 Correct 86 ms 6952 KB Output is correct
3 Correct 55 ms 5068 KB Output is correct
4 Correct 56 ms 4988 KB Output is correct
5 Correct 75 ms 5804 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct
7 Incorrect 3724 ms 591604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6960 KB Output is correct
2 Correct 86 ms 6952 KB Output is correct
3 Correct 55 ms 5068 KB Output is correct
4 Correct 56 ms 4988 KB Output is correct
5 Correct 75 ms 5804 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct
7 Correct 7512 ms 1580228 KB Output is correct
8 Correct 7426 ms 1580344 KB Output is correct
9 Correct 55 ms 4916 KB Output is correct
10 Correct 6640 ms 1580176 KB Output is correct
11 Correct 6803 ms 1580116 KB Output is correct
12 Correct 6731 ms 1580148 KB Output is correct
13 Correct 6740 ms 1580188 KB Output is correct
14 Correct 7060 ms 1580064 KB Output is correct
15 Correct 7087 ms 1580056 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 6294 ms 1580076 KB Output is correct
18 Correct 6431 ms 1580064 KB Output is correct
19 Correct 7184 ms 1580176 KB Output is correct
20 Correct 7129 ms 1580164 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 7125 ms 1580120 KB Output is correct
24 Correct 6279 ms 1580164 KB Output is correct
25 Correct 6375 ms 1580084 KB Output is correct
26 Incorrect 3724 ms 591604 KB Output isn't correct
27 Halted 0 ms 0 KB -