oj.uz

Submission #525256

# Submission time Handle Problem Language Result Execution time Memory
525256 2022-02-11T08:03:41 Z Aldas25 Road Construction (JOI21_road_construction) C++14
5 / 100
 10000 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";
}

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

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

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

  //  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}});
    }

    while (!q.empty()) {
        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 67 ms 6960 KB Output is correct
2 Correct 66 ms 6968 KB Output is correct
3 Correct 38 ms 5052 KB Output is correct
4 Correct 47 ms 5008 KB Output is correct
5 Correct 58 ms 5760 KB Output is correct
6 Correct 21 ms 4548 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10091 ms 226132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1847 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 1847 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 67 ms 6960 KB Output is correct
2 Correct 66 ms 6968 KB Output is correct
3 Correct 38 ms 5052 KB Output is correct
4 Correct 47 ms 5008 KB Output is correct
5 Correct 58 ms 5760 KB Output is correct
6 Correct 21 ms 4548 KB Output is correct
7 Runtime error 1615 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 67 ms 6960 KB Output is correct
2 Correct 66 ms 6968 KB Output is correct
3 Correct 38 ms 5052 KB Output is correct
4 Correct 47 ms 5008 KB Output is correct
5 Correct 58 ms 5760 KB Output is correct
6 Correct 21 ms 4548 KB Output is correct
7 Execution timed out 10091 ms 226132 KB Time limit exceeded
8 Halted 0 ms 0 KB -