제출 #1238750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238750		Gray	나일강 (IOI24_nile)	C++20	100 / 100	291 ms	96656 KiB

nile

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


struct DSU{
    struct node{
        multiset<pair<ll, ll>> odd, even;
        multiset<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(){
            even.swap(odd);
        }
        ll contr(){
            // cout << "AKA " << sumb << "&" << sz << ": ";
            ll res; assert((*odd.begin()).ff>0);
            if (!opt.empty()) assert(*opt.begin()>0);
            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[v].sz>a[u].sz) {
            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);
            }
            for (auto fr:a[u].opt){
                a[v].opt.insert(fr);
            }
            full+=a[v].contr();
        }else{
            p[v]=u;
            if (a[u].sz%2){
                // cout << "H" << endl;
                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);
            }
            for (auto fr:a[v].opt){
                a[u].opt.insert(fr);
            }
            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++){
	    vector<pair<ll, ll>> opts;
	    while (!mrgs.empty() and mrgs.back()[0]<=qs[i].ff) {

			// cout << a[mrgs.back()[1]][0] << " " << a[mrgs.back()[1]][1] << " " << a[mrgs.back()[1]][2] << " w ";
			// cout << a[mrgs.back()[2]][0] << " " << a[mrgs.back()[2]][1] << " " << a[mrgs.back()[2]][2] << ln;
			if (!tr.unite(mrgs.back()[1], mrgs.back()[2])){
			    ll ind = (mrgs.back()[1]+mrgs.back()[2])/2;
				opts.push_back({ind, a[ind][1]-a[ind][2]});
			}
			mrgs.pop_back();
		}
		for (auto [ind, xab]:opts){
		    tr.addopt(ind, xab);
		}
		// 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: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18