Submission #1181851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181851		sagnbaevv	Nile (IOI24_nile)	C++17	100 / 100	73 ms	16700 KiB

nile

#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
#define el '\n'

const int N = 1e6 + 24;

struct Node {
    ll w, a, b;
};
 
struct Edge {
    int u, v; ll w;
    Edge() {};
    Edge(int u_, int v_, ll w_): u(u_), v(v_), w(w_) {}
};
 
vector<int> par, sz, ch, le;
vector<ll> sum, mn, even, odd;
 
Node p[N]; ll pf[N];

void init(int n) {
    par.resize(n + 1); sz.resize(n + 1); 
    ch.resize(n + 1); le.resize(n + 1);
    mn.resize(n + 1); sum.resize(n + 1);
    even.resize(n + 1), odd.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        par[i] = i, sz[i] = 1, ch[i] = i % 2, le[i] = i;
        odd[i] = even[i] = mn[i] = 1e18;
    }
}

int find(int v) {
    return (v == par[v] ? v : par[v] = find(par[v]));
}

bool join(int u, int v, ll d) {
    u = find(u), v = find(v);
    if (u != v) {
        if (sz[u] < sz[v]) swap(u, v);

        mn[u] = min(mn[u], mn[v]);
        odd[u] = min(odd[u], odd[v]);
        even[u] = min(even[u], even[v]);
        le[u] = min(le[u],le[v]);
 
        if ((sz[u] + sz[v]) % 2 == 1) {
            if (le[u] % 2 == 0) {
                ch[u] = 0;
            }
            else {
                ch[u] = 1;
            }
        }
        
        par[v] = u;
        sz[u] += sz[v]; 
        sum[u] += sum[v];
 
        return 1;
    }
    
    else return 0;
}

ll cost(int u) {
    u = find(u);
    if (sz[u] % 2 == 0) return sum[u];
    else {
        if (ch[u] == 0) return sum[u] + min(even[u], mn[u]);
        return sum[u] + min(odd[u], mn[u]);
    }
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size(); init(n);

    for (int i = 1; i <= n; i++) {
        p[i].w = W[i - 1];
        p[i].a = A[i - 1];
        p[i].b = B[i - 1];
    }

    sort(p + 1, p + n + 1, [](Node x, Node y) { return x.w < y.w; }); 

    for (int i = 1; i <= n; i++) {
        sum[i] = p[i].b;
        if (i % 2 == 1) odd[i] = p[i].a - p[i].b;
        else even[i] = p[i].a - p[i].b;
    }

    for (int i = 1; i <= n; i++) pf[i] = pf[i - 1] + p[i].a;

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

    vector<Edge> e, e2;
    for (int i = 2; i <= n; i++) {
        e.push_back(Edge(i, i - 1, p[i].w - p[i - 1].w));
    }
    for (int i = 3; i <= n; i++) {
        e2.push_back(Edge(i, i - 2, p[i].w - p[i - 2].w));
    }
    sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w < b.w; });
    sort(e2.begin(), e2.end(), [](Edge a, Edge b) { return a.w < b.w; });

    vector<ll> R(q);
    int i = 0, i2 = 0; ll res = 0; 
    for (int i = 1; i <= n; i++) res += p[i].a;
    
    for (int j = 0; j < q; j++) {
        while (i < e.size() && e[i].w <= qr[j].first) {
            if (find(e[i].u) != find(e[i].v)) {
                res -= cost(e[i].u);
                res -= cost(e[i].v);
                join(e[i].u, e[i].v, qr[j].first);
                res += cost(e[i].u);
            }
            i++;
        }
        while (i2 < e2.size() && e2[i2].w <= qr[j].first) {
            res -= cost(e2[i2].u);
            mn[find(e2[i2].u - 1)] = min(mn[find(e2[i2].u - 1)], p[e2[i2].u - 1].a - p[e2[i2].u - 1].b);
            res += cost(e2[i2].u);
            i2++;
        }
        R[qr[j].second] = res;
    }
    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