oj.uz

Submission #525258

# Submission time Handle Problem Language Result Execution time Memory
525258 2022-02-11T08:08:31 Z Aldas25 Road Construction (JOI21_road_construction) C++14
11 / 100
 1911 ms 2097156 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 250100, MAXK = 20;
const ll MOD = 1e9+7;

int n, k;
ll x[MAXN], y[MAXN];

ll dst (int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

vector<ll> d;

void solve1 () {
    FOR(i, 1, n) FOR(j, i+1, n)
        d.pb(dst(i, j));

    sort(d.begin(), d.end());
    FOR(i, 0, k-1)
        cout << d[i] << "\n";

    //exit(1);
}

//int toLe[MAXN], toRi[MAXN];

priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> q;

void solve2 () {
    sort(x+1, x+n+1);


  //  FOR(i, 1, n) toLe[i] = toRi[i] = i;

    FOR(i, 1, n-1) {
        ll d = dst(i, i+1);
        q.push({d, {i,i+1}});
    }

    REP(k) {
        auto p = q.top();
        q.pop();
        ll d = p.f;
        int i = p.s.f, j = p.s.s;

        cout << d << "\n";

        if (j < n) {
            q.push({dst(i, j+1), {i,j+1}});
        }
    }


    //cout << " ksdfsdf" << endl;
}

int main()
{
    FAST_IO;

    cin >> n >> k;
    FOR(i, 1, n) cin >> x[i] >> y[i];

    bool sub2 = true;
    FOR(i, 1, n) if (y[i] != 0) sub2 = false;

    if (sub2) solve2();
    else solve1();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6964 KB Output is correct
2 Correct 63 ms 6972 KB Output is correct
3 Correct 40 ms 5016 KB Output is correct
4 Correct 38 ms 5064 KB Output is correct
5 Correct 58 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 150 ms 12508 KB Output is correct
2 Correct 152 ms 12472 KB Output is correct
3 Correct 42 ms 2812 KB Output is correct
4 Correct 121 ms 12332 KB Output is correct
5 Correct 96 ms 12460 KB Output is correct
6 Correct 101 ms 12592 KB Output is correct
7 Correct 100 ms 11828 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1911 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1911 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6964 KB Output is correct
2 Correct 63 ms 6972 KB Output is correct
3 Correct 40 ms 5016 KB Output is correct
4 Correct 38 ms 5064 KB Output is correct
5 Correct 58 ms 5804 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct
7 Runtime error 1580 ms 2097156 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6964 KB Output is correct
2 Correct 63 ms 6972 KB Output is correct
3 Correct 40 ms 5016 KB Output is correct
4 Correct 38 ms 5064 KB Output is correct
5 Correct 58 ms 5804 KB Output is correct
6 Correct 24 ms 4548 KB Output is correct
7 Correct 150 ms 12508 KB Output is correct
8 Correct 152 ms 12472 KB Output is correct
9 Correct 42 ms 2812 KB Output is correct
10 Correct 121 ms 12332 KB Output is correct
11 Correct 96 ms 12460 KB Output is correct
12 Correct 101 ms 12592 KB Output is correct
13 Correct 100 ms 11828 KB Output is correct
14 Runtime error 1911 ms 2097156 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -