oj.uz

Submission #396371

# Submission time Handle Problem Language Result Execution time Memory
396371 2021-04-29T20:54:41 Z 4fecta Road Construction (JOI21_road_construction) C++17
38 / 100
 7484 ms 669820 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)

struct piii {
    int f, s, boom;
};

const int MN = 250005;

int n, k, perm[MN], rev[MN];
pii a[MN];

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

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

bool cmp1(int p, int q) {
    if (a[p].s != a[q].s) return a[p].s < a[q].s;
    return a[p].f < a[q].f;
}

int32_t main() {
    boost();

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].f >> a[i].s, perm[i] = i;
    sort(perm + 1, perm + n + 1, cmp1);
    for (int i = 1; i <= n; i++) rev[perm[i]] = i;
    //for (int i = 1; i <= n; i++) printf("%d\n", perm[i]);
    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<piii, vector<piii>, decltype(&cmp)> q(cmp);
    set<pii> vis;
    for (int gap = 1; gap <= 20; gap++) {
        for (int i = gap + 1; i <= n; i++) q.push({i - gap, i, 0}), vis.insert({i - gap, i});
    }
    for (int gap = 1; gap <= 10; gap++) {
        for (int i = gap + 1; i <= n; i++) if (!vis.count({min(perm[i - gap], perm[i]), max(perm[i - gap], perm[i])})) q.push({perm[i - gap], perm[i], 1}), vis.insert({min(perm[i - gap], perm[i]), max(perm[i - gap], perm[i])});
    }
    while (q.size() && k--) {
        piii i = q.top(); q.pop();
        printf("%lld\n", cost(a[i.f], a[i.s]));
        if (i.boom) continue;
        if (i.s < n && !vis.count({i.f, i.s + 1})) q.push({i.f, i.s + 1, 0}), 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, 0}), vis.insert({i.f - 1, i.s});
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6932 KB Output is correct
2 Correct 82 ms 7088 KB Output is correct
3 Correct 55 ms 5016 KB Output is correct
4 Correct 56 ms 5012 KB Output is correct
5 Correct 76 ms 5816 KB Output is correct
6 Correct 25 ms 4548 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7484 ms 655028 KB Output is correct
2 Correct 7446 ms 655060 KB Output is correct
3 Correct 55 ms 4920 KB Output is correct
4 Correct 6920 ms 669820 KB Output is correct
5 Correct 6692 ms 655080 KB Output is correct
6 Correct 6699 ms 655232 KB Output is correct
7 Correct 6762 ms 654376 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6694 ms 654032 KB Output is correct
2 Correct 6644 ms 653772 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6345 ms 653832 KB Output is correct
5 Correct 6465 ms 653844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6694 ms 654032 KB Output is correct
2 Correct 6644 ms 653772 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6345 ms 653832 KB Output is correct
5 Correct 6465 ms 653844 KB Output is correct
6 Correct 6686 ms 653852 KB Output is correct
7 Correct 6714 ms 653872 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 6727 ms 653800 KB Output is correct
11 Correct 6374 ms 653848 KB Output is correct
12 Correct 6415 ms 653964 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6932 KB Output is correct
2 Correct 82 ms 7088 KB Output is correct
3 Correct 55 ms 5016 KB Output is correct
4 Correct 56 ms 5012 KB Output is correct
5 Correct 76 ms 5816 KB Output is correct
6 Correct 25 ms 4548 KB Output is correct
7 Incorrect 3308 ms 265816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6932 KB Output is correct
2 Correct 82 ms 7088 KB Output is correct
3 Correct 55 ms 5016 KB Output is correct
4 Correct 56 ms 5012 KB Output is correct
5 Correct 76 ms 5816 KB Output is correct
6 Correct 25 ms 4548 KB Output is correct
7 Correct 7484 ms 655028 KB Output is correct
8 Correct 7446 ms 655060 KB Output is correct
9 Correct 55 ms 4920 KB Output is correct
10 Correct 6920 ms 669820 KB Output is correct
11 Correct 6692 ms 655080 KB Output is correct
12 Correct 6699 ms 655232 KB Output is correct
13 Correct 6762 ms 654376 KB Output is correct
14 Correct 6694 ms 654032 KB Output is correct
15 Correct 6644 ms 653772 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 6345 ms 653832 KB Output is correct
18 Correct 6465 ms 653844 KB Output is correct
19 Correct 6686 ms 653852 KB Output is correct
20 Correct 6714 ms 653872 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 6727 ms 653800 KB Output is correct
24 Correct 6374 ms 653848 KB Output is correct
25 Correct 6415 ms 653964 KB Output is correct
26 Incorrect 3308 ms 265816 KB Output isn't correct
27 Halted 0 ms 0 KB -