oj.uz

Submission #396370

# Submission time Handle Problem Language Result Execution time Memory
396370 2021-04-29T20:52:28 Z 4fecta Road Construction (JOI21_road_construction) C++17
38 / 100
 5240 ms 562204 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 <= 5; 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 83 ms 6960 KB Output is correct
2 Correct 81 ms 6916 KB Output is correct
3 Correct 55 ms 5048 KB Output is correct
4 Correct 56 ms 5016 KB Output is correct
5 Correct 86 ms 5820 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 5240 ms 547800 KB Output is correct
2 Correct 5191 ms 547588 KB Output is correct
3 Correct 56 ms 4888 KB Output is correct
4 Correct 4540 ms 562204 KB Output is correct
5 Correct 4438 ms 547576 KB Output is correct
6 Correct 4481 ms 547472 KB Output is correct
7 Correct 4558 ms 546804 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4407 ms 546376 KB Output is correct
2 Correct 4519 ms 546320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4086 ms 546364 KB Output is correct
5 Correct 4136 ms 546348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4407 ms 546376 KB Output is correct
2 Correct 4519 ms 546320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4086 ms 546364 KB Output is correct
5 Correct 4136 ms 546348 KB Output is correct
6 Correct 4352 ms 546400 KB Output is correct
7 Correct 4330 ms 546244 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 4382 ms 546256 KB Output is correct
11 Correct 4064 ms 546476 KB Output is correct
12 Correct 4193 ms 546248 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6960 KB Output is correct
2 Correct 81 ms 6916 KB Output is correct
3 Correct 55 ms 5048 KB Output is correct
4 Correct 56 ms 5016 KB Output is correct
5 Correct 86 ms 5820 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct
7 Incorrect 2513 ms 233268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6960 KB Output is correct
2 Correct 81 ms 6916 KB Output is correct
3 Correct 55 ms 5048 KB Output is correct
4 Correct 56 ms 5016 KB Output is correct
5 Correct 86 ms 5820 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct
7 Correct 5240 ms 547800 KB Output is correct
8 Correct 5191 ms 547588 KB Output is correct
9 Correct 56 ms 4888 KB Output is correct
10 Correct 4540 ms 562204 KB Output is correct
11 Correct 4438 ms 547576 KB Output is correct
12 Correct 4481 ms 547472 KB Output is correct
13 Correct 4558 ms 546804 KB Output is correct
14 Correct 4407 ms 546376 KB Output is correct
15 Correct 4519 ms 546320 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 4086 ms 546364 KB Output is correct
18 Correct 4136 ms 546348 KB Output is correct
19 Correct 4352 ms 546400 KB Output is correct
20 Correct 4330 ms 546244 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 4382 ms 546256 KB Output is correct
24 Correct 4064 ms 546476 KB Output is correct
25 Correct 4193 ms 546248 KB Output is correct
26 Incorrect 2513 ms 233268 KB Output isn't correct
27 Halted 0 ms 0 KB -