제출 #1220798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220798		cjoa	나일강 (IOI24_nile)	C++20	100 / 100	84 ms	12604 KiB

nile

#include "nile.h"

#include <vector>
#include <queue>
#include <algorithm>
#include <array>
#include <iostream>
#include <cassert>

using namespace std;

using II = pair<int,int>;
using III = tuple<int,int,int>;

const int INF = 1e9 + 123;

struct DisjointSet {
    vector<int> par;
    vector<int> sz;
    vector< array<int,3> > min_cost;
    long long total_cost;
    DisjointSet(vector<int> _cost) : par(_cost.size(), -1), sz(_cost.size(), 1) {
        total_cost = 0;
        for (int c : _cost) {
            min_cost.push_back({c, INF, INF});
            total_cost += c;
        }
    }
    int find(int x, bool trace = false) {
        if (par[x] < 0) return x;
        return par[x] = find(par[x]);
    }

    void update_extra_cost(int x, int c) {
        x = find(x);
        if (sz[x] % 2 == 1) {
            total_cost -= min( min_cost[x][0], min_cost[x][2] );
        }
        min_cost[x][2] = min(min_cost[x][2], c);
        if (sz[x] % 2 == 1) {
            total_cost += min( min_cost[x][0], min_cost[x][2] );
        }
    }

    void join(int x, int y) {
        x = find(x);
        y = find(y);
        assert(x != y);

        if (sz[y] % 2 == 1) {
            // remove cost of y component
            total_cost -= min( min_cost[y][0], min_cost[y][2] );
        }
        if (sz[x] % 2 == 1) {
            // remove cost of x component
            total_cost -= min( min_cost[x][0], min_cost[x][2] );
        }

        if (sz[x] % 2 == 0) {
            min_cost[x][0] = min(min_cost[x][0], min_cost[y][0]);
            min_cost[x][1] = min(min_cost[x][1], min_cost[y][1]);
        }
        else {
            min_cost[x][0] = min(min_cost[x][0], min_cost[y][1]);
            min_cost[x][1] = min(min_cost[x][1], min_cost[y][0]);
        }
        min_cost[x][2] = min(min_cost[x][2], min_cost[y][2]);

        par[y] = x;
        sz[x] += sz[y];

        if (sz[x] % 2 == 1) {
            total_cost += min( min_cost[x][0], min_cost[x][2] );
        }
    }
};

struct Artifact {
    int weight;
    int cost;
};


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B,
                                  vector<int> E) {
    // Full solution

    const int N = W.size();
    if (N == 1)
        return vector<long long>(N, A[0]);

    long long base_cost = 0;
    for (int i = 0; i < N; i++)
        base_cost += B[i];

    cerr << "base_cost: " << base_cost << endl;

    const int Q = E.size();
    vector<long long> R(Q, base_cost);

    vector<Artifact> artifacts;
    for (int i = 0; i < N; i++)
        artifacts.push_back({W[i], A[i]-B[i]});

    sort(artifacts.begin(), artifacts.end(),
         [&] (Artifact a, Artifact b) -> bool {return a.weight < b.weight; });

    vector<int> C(N);
    for (int i = 0; i < N; i++)
        C[i] = artifacts[i].cost;

    priority_queue< III, vector<III>, greater<III> > events;
    for (int i = 0; i < N-1; ++i)
        events.emplace( artifacts[i+1].weight - artifacts[i].weight, i, 1 );
    for (int i = 0; i < N-2; ++i)
        events.emplace( artifacts[i+2].weight - artifacts[i].weight, i, 2 );

    priority_queue< II, vector<II>, greater<II> > sorted_queries;
    for (int j = 0; j < Q; j++)
        sorted_queries.emplace( E[j], j );

    DisjointSet dset(C);
    while (!sorted_queries.empty()) {
        auto [e, j] = sorted_queries.top(); sorted_queries.pop();
        while (!events.empty()) {
            auto [wdif, i, t] = events.top();
            if (wdif > e) break;
        //  cerr << "wdif: " << wdif << "  i: " << i << "  t: " << t << endl;
            events.pop();
            if (t == 1)
                dset.join(i, i+1);
            else
                dset.update_extra_cost(i, artifacts[i+1].cost);
        }
        R[j] += dset.total_cost;
    }

    return R;
}

• 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