Submission #525258

#	Time	Username	Problem	Language	Result	Execution time	Memory
525258		Aldas25	Road Construction (JOI21_road_construction)	C++14	11 / 100	1911 ms	2097156 KiB

road_construction

#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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35