Submission #1220741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220741		cjoa	Nile (IOI24_nile)	C++20	32 / 100	61 ms	7364 KiB

nile

#include "nile.h"

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

using namespace std;

using II = pair<int,int>;

struct DisjointSet {
    vector<int> par;
    vector<int> sz;
    int cnt_odd_size_comp;
    DisjointSet(int _N) : par(_N, -1), sz(_N, 1), cnt_odd_size_comp(_N) {}
    int find(int x) {
        if (par[x] < 0) return x;
        return par[x] = find(par[x]);
    }
    void join(int x, int y) {
        x = find(x);
        y = find(y);
        if (sz[x] < sz[y])
            swap(x, y);
        par[y] = x;
        if (sz[y] % 2 == 1)
            --cnt_odd_size_comp;
        if (sz[x] % 2 == 1)
            --cnt_odd_size_comp;
        sz[x] += sz[y];
        if (sz[x] % 2 == 1)
            ++cnt_odd_size_comp;
    }
};

struct Artifact {
    int weight;
    int cost;
};


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B,
                                  vector<int> E) {
    // subtask 6: A[i] = 2, B[i] = 1

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

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

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

    DisjointSet dset(N);
    while (!sorted_queries.empty()) {
        auto [e, j] = sorted_queries.top(); sorted_queries.pop();
        while (!events.empty()) {
            auto [wdif, i] = events.top();
            if (wdif > e) break;
            events.pop();
            dset.join(i, i+1);
        }
        R[j] += dset.cnt_odd_size_comp;
    }

    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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