Submission #1034128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034128		_8_8_	Road Closures (APIO21_roads)	C++17	0 / 100	2055 ms	11088 KiB

roads

#include "roads.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> d,u,v;

int get(int i,int k){
    int ans = (d[u[i]] > k) + (d[v[i]] > k);
    return ans;
}
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W) {
    u = U;
    v = V;
    vector<int> deg(N,0);
    for(int i = 0;i < N - 1;i++){
        deg[U[i]]++;
        deg[V[i]]++;
    }
    vector<ll> ans;
    for(int i = 0;i < N;i++){
        d = deg;
        set<pair<ll,int>> st;
        for(int j = 0;j < N - 1;j++){
            st.insert({0,j});
        }
        ll res =0;
        while(!st.empty()){
            auto[c,j] = (*st.begin());
            st.erase({c,j});
            ll _ = get(j,i),rc = W[j];
            // cout << j << ' ' << _ << '\n';
            if(_ == 0) continue;
            if(_ == 1) rc = rc + rc;
            if(c != rc){
                st.insert({rc,j});
                continue;
            }
            res += W[j];
            d[u[j]]--;
            d[v[j]]--;
        }
        // cout << '\n';
        ans.push_back(res);
    }
    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