oj.uz

Submission #959913

# Submission time Handle Problem Language Result Execution time Memory
959913 2024-04-09T10:09:42 Z alextodoran Road Construction (JOI21_road_construction) C++17
13 / 100
 2009 ms 73044 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 250000;

int N, K;
ll X[N_MAX + 2], Y[N_MAX + 2];
int order_x[N_MAX + 2], order_y[N_MAX + 2];
int nxt_x[N_MAX + 2], nxt_y[N_MAX + 2];

struct Candidate {
    int i, j;
    ll dist;
    Candidate (const int &_i, const int &_j) {
        i = _i; j = _j;
        if (i > j) {
            swap(i, j);
        }
        dist = max(abs(X[i] - X[j]), abs(Y[i] - Y[j]));
    }
};
bool operator < (const Candidate &a, const Candidate &b) {
    return make_tuple(a.dist, a.i, a.j) < make_tuple(b.dist, b.i, b.j);
}
set <Candidate> cands;

int curr_x[N_MAX + 2], curr_y[N_MAX + 2];

set <pair <int, int>> seen;

void update (int i) {
    curr_x[i] = nxt_x[curr_x[i]];
    curr_y[i] = nxt_y[curr_y[i]];
    if (curr_x[i] != 0) {
        cands.insert(Candidate(i, curr_x[i]));
    }
    if (curr_y[i] != 0) {
        cands.insert(Candidate(i, curr_y[i]));
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        ll x, y;
        cin >> x >> y;
        X[i] = y + x; Y[i] = y - x;
    }
    iota(order_x + 1, order_x + N + 1, 1);
    iota(order_y + 1, order_y + N + 1, 1);
    sort(order_x + 1, order_x + N + 1, [&] (const int &i, const int &j) {
        return X[i] < X[j];
    });
    sort(order_y + 1, order_y + N + 1, [&] (const int &i, const int &j) {
        return Y[i] < Y[j];
    });
    for (int i = 1; i <= N; i++) {
        nxt_x[order_x[i]] = order_x[i + 1];
        nxt_y[order_y[i]] = order_y[i + 1];
    }
    for (int i = 1; i <= N; i++) {
        curr_x[i] = curr_y[i] = i;
        update(i);
    }
    while (K--) {
        Candidate best = *cands.begin();
        int i = best.i, j = best.j; ll dist = best.dist;
        cands.erase(cands.begin());
        if (seen.find(make_pair(i, j)) != seen.end()) {
            K++; continue;
        }
        seen.insert(make_pair(i, j));
        cout << dist << "\n";
        update(i); update(j);
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 659 ms 36292 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 2009 ms 69364 KB Output is correct
2 Correct 1906 ms 69104 KB Output is correct
3 Correct 365 ms 24196 KB Output is correct
4 Correct 1118 ms 73044 KB Output is correct
5 Correct 1068 ms 57824 KB Output is correct
6 Correct 1068 ms 57732 KB Output is correct
7 Correct 1054 ms 57324 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 46404 KB Output is correct
2 Correct 483 ms 46524 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 234 ms 28772 KB Output is correct
5 Correct 459 ms 46660 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 46404 KB Output is correct
2 Correct 483 ms 46524 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 234 ms 28772 KB Output is correct
5 Correct 459 ms 46660 KB Output is correct
6 Incorrect 485 ms 46560 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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