Submission #1185971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185971		gyg	Nile (IOI24_nile)	C++20	38 / 100	192 ms	62760 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed 
#define int long long
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5, INF = 1e18;

int n;
arr<pii, N> a;

vec<vec<int>> edg;
struct Dsj {
    arr<int, N> pr;
    arr<set<pii>, N> st;
    arr<int, N> sm;

    void intl() {
        for (int u = 1; u <= n; u++)
            pr[u] = u, st[u] = {{a[u].sec, u}}, sm[u] = a[u].sec;
    }
    void mrg(int u, int v) {
        u = pr[u], v = pr[v];
        assert(u != v);
        if (st[u].size() < st[v].size()) swap(u, v);
        for (pii x : st[v]) {
            pr[x.sec] = u;
            st[u].insert(x);
            sm[u] += x.fir;
        }
    }
    int evl(int u) {
        u = pr[u];
        int ans = sm[u];
        if (st[u].size() % 2 == 1) ans -= st[u].begin()->fir;
        return ans;
    }
} dsj;

vec<int> calculate_costs(vec<sig> _ps, vec<sig> _fl, vec<sig> _pr, vec<sig> _qr) {
    n = _ps.size();
    int whl = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = {_ps[i - 1], _fl[i - 1] - _pr[i - 1]};
        whl += _fl[i - 1];
    }
    sort(a.begin() + 1, a.begin() + n + 1);

    for (int i = 1; i <= n - 1; i++)
        edg.push_back({a[i + 1].fir - a[i].fir, i, i + 1});
    sort(edg.begin(), edg.end());
    dsj.intl();

    vec<pii> crt = {{0, 0}}; 
    int sm = 0;
    for (vec<int> x : edg) {
        int d = x[0], u = x[1], v = x[2];
        if (dsj.pr[u] == dsj.pr[v]) continue;
        sm -= dsj.evl(u), sm -= dsj.evl(v);
        dsj.mrg(u, v);
        sm += dsj.evl(u);
        crt.push_back({d, sm});
    }

    vec<int> ans;
    for (int d : _qr) {
        int lw = 0, hg = crt.size() - 1;
        while (lw < hg) {
            int md = (lw + hg + 1) / 2;
            if (d >= crt[md].fir) lw = md;
            else hg = md - 1;
        }
        ans.push_back(whl - crt[lw].sec);
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18