Submission #979431

#	Time	Username	Problem	Language	Result	Execution time	Memory
979431		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	2050 ms	23888 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<int,ll>> adj[100100];
pair<ll,ll> dfs(int n,int p,int k){
    int ans1=0,ans2=0,h1=!!n,h2=0;
    priority_queue<int>pq;
    for(auto[a,b]:adj[n]){
        if(a==p)continue;
        auto[x,y]=dfs(a,n,k);
        y+=b;
        ans1+=min(x,y);
        ans2+=min(x,y);
        if(x<y)h1++,h2++,pq.push(x-y);
    }
    while(pq.size()){
        if(h1>k)
            ans1-=pq.top(),h1--;
        if(h2>k)
            ans2-=pq.top(),h2--;
        pq.pop();
    }
    return {ans1,ans2};
}
std::vector<ll> minimum_closure_costs(int N, std::vector<int> U,std::vector<int> V,std::vector<int> W) {
    vector<ll> ans(N,0);
    for(int i=0;i<N-1;i++) ans[0]+=W[i],
        adj[U[i]].push_back({V[i],W[i]}),
        adj[V[i]].push_back({U[i],W[i]});
    int mx=0;
    for(int i=0;i<N;i++)
        mx=max(mx,(int)adj[i].size());
    for(int i=1;i<mx;i++)
        ans[i]=dfs(0,0,i).first;
    return ans;
}

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