Submission #552201

#	Time	Username	Problem	Language	Result	Execution time	Memory
552201		marsxiang5902	Road Closures (APIO21_roads)	C++17	7 / 100	2094 ms	29516 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];

struct KMin{
    multiset<ll> st; int k;
    void init(int _k){ st.clear(); k = _k; }
    void insert(ll x){ st.insert(x); }
    void erase(ll x){ st.erase(st.find(x)); }
    void decK(){ assert(k--); }
    ll query(){
        assert(st.size() >= k);
        ll ret = 0;
        int i = 0;
        for(auto it = st.begin(); i < k; i++, it++)
            ret += *it;
        return ret;
    }
} kMin;

void dfs(int u){
    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);
    }
    diffs[u].resize(sz[u]);
    kMin.init(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);
            if(diffs[v][k] > w)
                ans[k] += w - diffs[v][k];
            kMin.insert(max(0LL, w - diffs[v][k]));
        }
        assert(kMin.k == sz[u] - k);
        ll res1 = kMin.query();
        kMin.decK();
        ll res2 = kMin.query();
        ans[k] += res1;
        diffs[u][k] = res1 - res2;
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.insert(w);
            kMin.erase(max(0LL, 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);
    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

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from roads.cpp:1:
roads.cpp: In member function 'll KMin::query()':
roads.cpp:16:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |         assert(st.size() >= k);
      |                ~~~~~~~~~~^~~~

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