제출 #1236258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236258		iwouldnt	Nile (IOI24_nile)	C++20	100 / 100	68 ms	13996 KiB

nile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
const ll INF = (ll)1e18;
const int MAXN = 100000;

int n, q;
ll baseB, extraCost;

struct Artifact { ll a, b, w; };
struct Edge    { int u, v; ll cost; };

vector<Artifact> artifacts;
vector<Edge> edges;        // holds both (i,i+1) and (i,i+2)
vector<int> parent, sz, minIdx;
vector<ll> minPar, minImpar, minBr;

int findRoot(int u) {
    return parent[u] == u ? u : parent[u] = findRoot(parent[u]);
}

ll compCost(int r) {
    if (sz[r] % 2 == 0) return 0;
    ll byParity = (minIdx[r] % 2 == 0 ? minPar[r] : minImpar[r]);
    return min(byParity, minBr[r]);
}

void unify(int u, int v) {
    int ru = findRoot(u), rv = findRoot(v);
    if (ru == rv) return;
    extraCost -= compCost(ru) + compCost(rv);
    if (sz[ru] > sz[rv]) swap(ru, rv);
    parent[ru] = rv;
    sz[rv] += sz[ru];
    minIdx[rv]   = min(minIdx[rv],   minIdx[ru]);
    minPar[rv]   = min(minPar[rv],   minPar[ru]);
    minImpar[rv] = min(minImpar[rv], minImpar[ru]);
    minBr[rv]    = min(minBr[rv],    minBr[ru]);
    extraCost += compCost(rv);
}

void applyBrincable(int mid) {
    int r = findRoot(mid);
    extraCost -= compCost(r);
    ll d = artifacts[mid].a - artifacts[mid].b;
    minBr[r] = min(minBr[r], d);
    extraCost += compCost(r);
}

vector<ll> calculate_costs(
    vector<int> W, vector<int> A,
    vector<int> B, vector<int> E
) {
    n = W.size(); q = E.size();
    artifacts.resize(n);
    baseB = 0;
    for (int i = 0; i < n; i++) {
        artifacts[i] = { (ll)A[i], (ll)B[i], (ll)W[i] };
        baseB += B[i];
    }

    // sort artifacts by weight
    sort(artifacts.begin(), artifacts.end(),
         [](auto &x, auto &y){ return x.w < y.w; });

    // build edges for (i, i+1) and (i, i+2)
    edges.clear();
    for (int i = 0; i + 1 < n; i++)
        edges.push_back({ i, i+1,
            abs(artifacts[i+1].w - artifacts[i].w) });
    for (int i = 0; i + 2 < n; i++)
        edges.push_back({ i, i+2,
            abs(artifacts[i+2].w - artifacts[i].w) });
    sort(edges.begin(), edges.end(),
         [](auto &x, auto &y){ return x.cost < y.cost; });

    // init DSU arrays
    parent.resize(n); sz.resize(n);
    minIdx.resize(n);
    minPar.assign(n, INF);
    minImpar.assign(n, INF);
    minBr.assign(n, INF);
    extraCost = 0;

    for (int i = 0; i < n; i++) {
        parent[i]   = i;
        sz[i]       = 1;
        minIdx[i]   = i;
        ll d = artifacts[i].a - artifacts[i].b;
        if (i % 2 == 0) minPar[i] = d;
        else            minImpar[i] = d;
        extraCost += d;
    }

    // prepare queries
    vector<pair<int,int>> queries(q);
    for (int i = 0; i < q; i++)
        queries[i] = { E[i], i };
    sort(queries.begin(), queries.end());

    // two-pointer sweep
    vector<ll> answer(q);
    int ei = 0;        // index in edges
    for (auto &qr : queries) {
        int D = qr.first, qi = qr.second;
        while (ei < (int)edges.size() && edges[ei].cost <= D) {
            auto &e = edges[ei++];
            if (e.v == e.u + 1) {
                // merge adjacent
                unify(e.u, e.v);
            } else {
                // enable brincable at mid = u+1
                applyBrincable(e.u+1);
            }
        }
        answer[qi] = baseB + extraCost;
    }

    return answer;
}

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