Submission #1278628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278628		Bui_Quoc_Cuong	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	8696 KiB

nile

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int n, q;
array <int, 3> a[maxn];
int lab[maxn];

int val[maxn], max_val[maxn];
long long ans = 0;

int find (int x) {
    return lab[x] < 0 ? x : lab[x] = find(lab[x]);
}

bool joint (int u, int v) {
    int x = find(u), y = find(v);
    if (x == y) return 0;

    int sz_x = abs(lab[x]);
    int sz_y = abs(lab[y]);

    if (sz_x == 1) {

    } else {
        ans-= val[x];
        if (sz_x & 1) {
            ans+= max_val[x];
        } else {

        }
    }

    if (sz_y == 1) {

    } else {
        ans-= val[y];
        if (sz_y & 1) {
            ans+= max_val[y];
        }
    }

    max_val[x] = max(max_val[x], max_val[y]);
    val[x]+= val[y];


    lab[x]+= lab[y];
    lab[y] = x;

    if (abs(lab[x]) & 1) {
        ans-= max_val[x];
    }
    ans+= val[x];

    return 1;
}

long long getAns (int D) {
    for (int i = 1; i <= n; i++) {
        lab[i] = - 1;
        max_val[i] = a[i][2] - a[i][1];
        val[i] = a[i][2] - a[i][1];
    }

    vector <array <int, 3>> sorted;
    for (int i = 2; i <= n; i++) {
        sorted.push_back({abs(a[i][0] - a[i - 1][0]), i - 1, i});
    }

    ans = 0;
    for (int i = 1; i <= n; i++) ans+= a[i][1];

    for (auto [w, u, v] : sorted) {
        if (w <= D) {
            joint (u, v);
        }
    }

    return ans;
}

vector <long long> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) {
    vector <long long> res;
    n = W.size();
    q = E.size();
    for (int i = 1; i <= n; i++) {
        a[i][0] = W[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        a[i][1] = A[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        a[i][2] = B[i - 1];
    }
    sort(a + 1, a + 1 + n);

    for (auto d : E) {
        res.push_back(getAns(d));
    }

    return res;
}

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