oj.uz

Submission #396358

# Submission time Handle Problem Language Result Execution time Memory
396358 2021-04-29T20:17:19 Z 4fecta Road Construction (JOI21_road_construction) C++17
33 / 100
 5490 ms 997256 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 <= 1) {
        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 <= 50; 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
0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5485 ms 984072 KB Output is correct
2 Correct 5490 ms 983840 KB Output is correct
3 Correct 287 ms 19000 KB Output is correct
4 Correct 4559 ms 997256 KB Output is correct
5 Correct 4550 ms 983788 KB Output is correct
6 Correct 4560 ms 983796 KB Output is correct
7 Correct 4656 ms 983132 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4662 ms 982588 KB Output is correct
2 Correct 4674 ms 982488 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4093 ms 982496 KB Output is correct
5 Correct 4201 ms 982560 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4662 ms 982588 KB Output is correct
2 Correct 4674 ms 982488 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4093 ms 982496 KB Output is correct
5 Correct 4201 ms 982560 KB Output is correct
6 Correct 4694 ms 982524 KB Output is correct
7 Correct 4683 ms 987736 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 4646 ms 987620 KB Output is correct
11 Correct 4083 ms 985436 KB Output is correct
12 Correct 4185 ms 987864 KB Output is correct

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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