Submission #1166556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166556		Sang	Nile (IOI24_nile)	C++20	38 / 100	61 ms	14776 KiB

nile

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, a[N], b[N];
ii w[N];

struct DSU{
    vi lab, mi, s;
    int ans = 0;
    DSU(int n) : lab(n), mi(n), s(n) {};

    void make_set(int u){
        lab[u] = -1;
        mi[u] = a[u] - b[u];
        s[u] = a[u] - b[u];
    }

    int get(int u){
        if ((-lab[u]) & 1) return s[u] - mi[u];
        return s[u];
    }

    int Find(int u){
        return lab[u] < 0 ? u : lab[u] = Find(lab[u]);
    }

    void Union(int u, int v){
        if ((u = Find(u)) == (v = Find(v))) return;
        if (lab[u] < lab[v]) swap(u, v);
        ans -= get(u) + get(v);
        lab[u] += lab[v];
        lab[v] = u;
        mi[u] = min(mi[u], mi[v]);
        s[u] += s[v];
        ans += get(u);
    }
};

vector<int> calculate_costs(vector<int32_t> W, vector<int32_t> A, vector<int32_t> B, vector<int32_t> E){
    n = A.size();
    int s = 0;
    FOR (i, 1, n){
        w[i] = {W[i-1], i};
        a[i] = A[i-1];
        b[i] = B[i-1];
        s += a[i];
    }
    sort(w + 1, w + n + 1);
    vector<pii> edges;
    FOR (i, 1, n - 1) edges.pb({w[i+1].fi - w[i].fi, {w[i].se, w[i+1].se}});
    DSU dsu(n + 5);
    FOR (i, 1, n) dsu.make_set(i);
    vector<ii> queries;
    FOR (i, 0, (int)E.size() - 1) queries.pb({E[i], i});
    sort(ALL(queries), greater<ii>());
    sort(ALL(edges), greater<pii>());
    vector<int> ans(E.size(), 0);
    while (!queries.empty()){
        while (!edges.empty() && edges.back().fi <= queries.back().fi){
            dsu.Union(edges.back().se.fi, edges.back().se.se);
            edges.pop_back();
        }
        ans[queries.back().se] = s - dsu.ans;
        queries.pop_back();
    }
    return ans;
}

#ifdef _Pbrngw_
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    vi ans = calculate_costs({15, 12, 2, 10, 21}, {5, 4, 5, 6, 3}, {1, 2, 2, 3, 2}, {5, 9, 1});
    for (int &x : ans) cout << x << '\n';
    return 0;
}
#endif // _Pbrngw_

• 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