Submission #979433

#	Time	Username	Problem	Language	Result	Execution time	Memory
979433		vjudge1	Road Closures (APIO21_roads)	C++17	5 / 100	45 ms	8912 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){
    ll ans1=0,ans2=0,h1=!!n,h2=0;
    priority_queue<ll>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);
    priority_queue<ll>pq;
    for(int i=0;i<N-1;i++)
        pq.push(-W[i]);
    for(int i=N-1;i--;)
        ans[i]=ans[i+1]-pq.top(),pq.pop();
    return ans;
}

• Subtask 1: 5 / 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