Submission #1238729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238729		Gray	Nile (IOI24_nile)	C++20	19 / 100	109 ms	43436 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;


struct DSU{
    struct node{
        set<pair<ll, ll>> odd, even;
        set<ll> opt;
        ll sumb, sz;
        node(){
            sumb=sz=0;
        }
        void addopt(ll xab){
            opt.insert(xab);
        }
        void addodd(ll xa, ll xb){
            sz++; odd.insert({xa-xb, xb}); sumb+=xb;
        }
        void addeven(ll xa, ll xb){
            sz++; even.insert({xa-xb, xb}); sumb+=xb;
        }
        void swapeo(){
            swap(odd, even);
        }
        ll contr(){
            ll res;
            if (sz%2) {
                if (!opt.empty()){
                    res=sumb+min(*opt.begin(), (*odd.begin()).ff);
                }else res=sumb+(*odd.begin()).ff;
            } else res= sumb;
            // cout << res << ln;
            return res;
        }
        // void debug(){
        //     for (auto x:odd) cout << x.ff << "-" << x.ss << "  ";
        //     cout << ln;
        //     for (auto x:even) cout << x.ff << "-" << x.ss << "  ";
        //     cout << ln;
        // }
    };
    vector<node> a;
    vector<ll> p; ll n, full;
    DSU(ll N, vector<array<ll, 3>> &b){
        n=N; p.resize(n, -1);
        a.resize(n); full=0;
        for (ll i=0; i<n; i++){
            a[i].addodd(b[i][1], b[i][2]); full+=a[i].contr();
        }
        // cout << "INIT: " << full << ln;
    }
    ll get(ll x){
        return p[x]==-1?x:p[x]=get(p[x]);
    }
    bool unite(ll u, ll v){
        u=get(u); v=get(v);
        if (u==v) return 0;
        assert(u<v);
        full-=a[u].contr(); full-=a[v].contr();
        if (a[u].odd.size()<a[v].odd.size()) {
            p[u]=v;
            if (a[u].sz%2){
                a[v].swapeo();
            }
            for (auto [xd, xb]:a[u].odd){
                a[v].addodd(xd+xb, xb);
            }
            for (auto [xd, xb]:a[u].even){
                a[v].addeven(xd+xb, xb);
            }
            full+=a[v].contr();
        }else{
            p[v]=u;
            if (a[u].sz%2){
                a[v].swapeo();
            }
            for (auto [xd, xb]:a[v].odd){
                a[u].addodd(xd+xb, xb);
            }
            for (auto [xd, xb]:a[v].even){
                a[u].addeven(xd+xb, xb);
            }
            full+=a[u].contr();
        }
        return 1;
    }
    void addopt(ll u, ll xab){
        u=get(u); full-=a[u].contr();
        a[u].addopt(xab); full+=a[u].contr();
    }
};


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	int q = (int)E.size(); int n = W.size();
	vector<ll> res(q);
	vector<array<ll, 3>> a(n);
	for (ll j=0; j<n; j++) a[j] = {W[j], A[j], B[j]};
	sort(a.begin(), a.end());
	DSU tr(n, a);
	vector<array<ll, 3>> mrgs;
	for (ll i=1; i<n; i++){
	    mrgs.push_back({a[i][0]-a[i-1][0], i-1, i});
		if (i-2>=0) mrgs.push_back({a[i][0]-a[i-2][0], i-2, i});
	}
	sort(mrgs.rbegin(), mrgs.rend());
	vector<pair<ll, ll>> qs(q);
	for (ll i=0; i<q; i++) qs[i] ={E[i], i};
	sort(qs.begin(), qs.end());
	for (ll i=0; i<q; i++){
	    while (!mrgs.empty() and mrgs.back()[0]<=qs[i].ff) {
			// cout << a[mrgs.back()[1]-1][0] << " " << a[mrgs.back()[1]-1][1] << " " << a[mrgs.back()[1]-1][2] << " w ";
			// cout << a[mrgs.back()[1]][0] << " " << a[mrgs.back()[1]][1] << " " << a[mrgs.back()[1]][2] << ln;
			if (!tr.unite(mrgs.back()[1], mrgs.back()[2])){
			    ll ind = (mrgs.back()[1]+mrgs.back()[2])/2;
				tr.addopt(ind, a[ind][1]-a[ind][2]);
			}
			mrgs.pop_back();
		}
		// cout << qs[i].ff << " -> " << tr.full << ln;
		res[qs[i].ss]=tr.full;
	}
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18