제출 #1231571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231571		shiocan	나일강 (IOI24_nile)	C++20	6 / 100	43 ms	11960 KiB

nile

#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
#define ull unsigned long long 
#define ld long double
#define ll long long
// #define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7; 
const ll inf = 1e18;
const int N = 1e5 + 50, K = 22;

// #include "nile.h"

ll n;
ll sum = 0;
vector<ll> c;
vector<pii> q;

struct dsu{
    vector<ll> sz, p, minodd, mineven, minidx, altmin;
    ll resodd = 0, reseven = 0;

    dsu(int n){
        sz = p = minodd = mineven = minidx = altmin = vector<ll> (n + 5, 0ll);
        for(int i = 0; i < n; i++)
            sz[i] = 1, p[i] = i, minodd[i] = mineven[i] = c[i], altmin[i] = inf, minidx[i] = i, resodd += c[i], reseven += c[i];
    }

    ll find(ll u){
        return p[u] == u ? u : p[u] = find(p[u]);
    }

    bool merge(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b)
            return false;

        if(sz[a] < sz[b])
            swap(a, b); 
        
        p[b] = a;

        resodd -= minodd[a];
        resodd -= minodd[b];

        reseven -= mineven[a];
        reseven -= mineven[b];

        minodd[a] = min(minodd[a], minodd[b]);
        mineven[a] = min(mineven[a], mineven[b]);
        minidx[a] = min(minidx[a], minidx[b]);
        altmin[a] = min(altmin[a], altmin[b]);
        sz[a] += sz[b];

        resodd += minodd[a];
        reseven += mineven[a];

        return true;
    }

    ll get(ll a){
        a = find(a);

        if(sz[a] % 2){
            if(minidx[a] % 2)
                return min(resodd, altmin[a]);
            else
                return min(reseven, altmin[a]);
        }

        return 0;
    }
};

struct item{
    ll w, a, b;
};
    
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
    n = a.size();
    c = vector<ll> (n, 0ll);
    vector<ll> ans((ll)e.size());

    for(auto i : b)
        sum += i;

    // ans = sum + cost(i)

    vector<item> arr(n);
    for(int i = 0; i < n; i++)  
        arr[i] = {w[i], a[i], b[i]};
    
    sort(all(arr), [](item x, item y){
        return x.w < y.w;
    });

    // cout << "arr: \n";
    // for(auto i : arr)
    //     cout << i.w << ' ' << i.a << ' ' << i.b << '\n';        
    // cout << '\n';

    for(int i = 0; i < n; i++)
        c[i] = arr[i].a - arr[i].b;

    // cout << "c: \n";
    // for(auto i : c)
    //     cout << i << ' ';
    // cout << '\n';

    for(int i = 0; i < e.size(); i++)
        q.push_back({e[i], i});

    sort(all(q));
    
    // cout << "q: \n";
    // for(auto i : q)
    //     cout << i.first << ' ' << i.second << '\n';
    // cout << '\n';

    vector<pii> p;
    for(int i = 0; i < n - 1; i++){
        p.push_back({i, i + 1});
        if(i + 2 < n)
            p.push_back({i, i + 2});
    }

    sort(all(p), [&](pii x, pii y){
        return arr[x.second].w - arr[x.first].w < arr[y.second].w - arr[y.first].w;        
    });

    // cout << "p: \n";
    // for(auto i : p)
    //     cout << arr[i.second].w - arr[i.first].w << ' ' << arr[i.first].w << ' ' << arr[i.second].w << ' ' << i.first << ' ' << i.second << '\n';
    // cout << '\n'; 

    dsu ds(n);

    int i = 0;
    for(auto [d, idx] : q){
        while(i < p.size() && arr[p[i].second].w - arr[p[i].first].w <= d){
            ds.merge(p[i].first, p[i].second);
            if(p[i].second - p[i].first == 2){
                ll x = ds.find(p[i].first + 1);
                // ds.altmin[x] = min(ds.altmin[x], c[p[i].first + 1]);
            }
            i++;
        }

        // for(auto k : ds.altmin) 
        //     cout << (k == inf ? -1 : k) << ' ';
        // cout << '\n';

        ans[idx] = sum + ds.get(p[0].first);
    }   

    // for(int i = 0; i < n; i++)
    //     cout << ds.get(i) << ' ';
    // cout << '\n';
    // ds.merge(1, 2);
    // ds.merge(2, 3);
    // // ds.merge(3, 4);
    // // ds.merge(0, 1);
    // for(int i = 0; i < n; i++)
    //     cout << ds.get(i) << ' ';
    // cout << '\n';
    /*


    */

    return ans;
}

void solve(){
    vector<int> w = {15, 12, 2, 10, 21};
    vector<int> a = {5, 4, 5, 6, 3};
    vector<int> b = {1, 2, 2, 3, 2};
    vector<int> e = {5, 9, 1};

    vector<ll> ans = calculate_costs(w, a, b, e);


    cout << '\n' << '\n' << "ans: ";
    for(auto i : ans)
        cout << i << ' ';
}

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