Submission #552210

#	Time	Username	Problem	Language	Result	Execution time	Memory
552210		marsxiang5902	도로 폐쇄 (APIO21_roads)	C++17	100 / 100	174 ms	48416 KiB

roads

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

using ll = long long;
const int MN = 1e5+5;

int N, sz[MN]; vector<pair<int,int>> adjl[MN]; ll ans[MN]; vector<ll> diffs[MN];
        
template <class T> void clr(T pq[]){
    assert(pq[0].size() >= pq[1].size());
    while(!pq[1].empty() && pq[1].top() == pq[0].top()){
        pq[1].pop();
        pq[0].pop();
    }
}

struct KMin{
    priority_queue<ll> iq[2]; priority_queue<ll, vector<ll>, greater<ll>> oq[2];
    int k, sz = 0; ll curSum = 0;
    KMin(int _k): k(_k){}
    void insert(ll x){
        curSum += x;
        iq[0].push(x);
        if(++sz > k){
            clr(iq);
            ll rem = iq[0].top(); iq[0].pop();
            oq[0].push(rem);
            curSum -= rem;
        }
    }
    void erase(ll x){
        assert(sz--);
        if(clr(iq); x <= iq[0].top()){
            curSum -= x;
            iq[1].push(x);
            if(sz >= k){
                clr(oq);
                ll ins = oq[0].top(); oq[0].pop();
                iq[0].push(ins);
                curSum += ins;
            }
        } else oq[1].push(x);
    }
    void decK(){ insert(0); }
    ll query(){ return curSum; }
};

void dfs(int u, int pw){
    sort(adjl[u].begin(), adjl[u].end(), [](pair<int,int> lhs, pair<int,int> rhs){
        return sz[lhs.first] > sz[rhs.first];
    });
    for(auto [v, w]: adjl[u]){
        adjl[v].erase(find(adjl[v].begin(), adjl[v].end(), pair(u, w)));
        dfs(v, w);
    }
    diffs[u].resize(sz[u]);
    KMin kMin(sz[u] - 1);
    for(auto [v, w]: adjl[u])
        kMin.insert(w);
    for(int k = 1; k < sz[u]; k++){
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.erase(w);
            kMin.insert(w - diffs[v][k]);
            assert(w >= diffs[v][k]);
        }
        ll res1 = kMin.query();
        kMin.decK();
        ll res2 = kMin.query();
        ans[k] += res1;
        diffs[u][k] = res1 - res2;
        ans[k] += min(0LL, pw - diffs[u][k]);
        diffs[u][k] = min(ll(pw), diffs[u][k]);
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.insert(w);
            kMin.erase(w - diffs[v][k]);
        }
    }
}

vector<ll> minimum_closure_costs(int _N, vector<int> us, vector<int> vs, 
    vector<int> ws){
    N = _N;
    for(int i = 0, u, v, w; i < N-1; i++){
        u = us[i]; v = vs[i]; w = ws[i];
        adjl[u].emplace_back(v, w);
        adjl[v].emplace_back(u, w);
    }
    for(int i = 0; i < N; i++)
        sz[i] = adjl[i].size();
    ++sz[0];
    dfs(0, 0);
    ans[0] = accumulate(ws.begin(), ws.end(), 0LL);
    for(int k = 1; k < sz[0]; k++)
        ans[k] -= diffs[0][k];
    return vector<ll>(ans, ans+N);
}

#ifdef LOCAL_PROJECT
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N; cin >> N;
    vector<int> us(N-1), vs(N-1), ws(N-1);
    for(int i = 0; i < N-1; i++)
        cin >> us[i] >> vs[i] >> ws[i];
    vector<ll> ans = minimum_closure_costs(N, us, vs, ws);
    for(int i = 0; i < N; i++)
        printf("%d%c", ans[i], " \n"[i==N-1]);

    return 0;
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22