Submission #624774

#	Time	Username	Problem	Language	Result	Execution time	Memory
624774		Lobo	Road Closures (APIO21_roads)	C++17	24 / 100	251 ms	6620 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x)  int32_t(x.size())
#define int long long
const int maxn = 2e3+10;
const int inf = 1e18+10;
int n, dp[maxn][2];
vector<int> g[maxn];
vector<pair<int,int>> gesp[maxn];

void dfs(int u, int qtd, int ant) {
    // mark[u] = qtd+1;
    int ans = 0;
    vector<int> use;
    for(auto V : gesp[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        dfs(v,qtd,u);
        ans+= min(dp[v][0],dp[v][1]+w);
        use.pb(-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w);
    }

    sort(all(use));
    //se nao tem a aresta com o pai -> sz(g[u])-1-qtd = t
    dp[u][0] = dp[u][1] = inf;
    if(sz(g[u])-qtd-1 <= 0) dp[u][1] = ans;
    if(sz(g[u])-qtd <= 0) dp[u][0] = ans;
    for(int i = 1; i <= sz(g[u])-qtd; i++) {
        ans+= use[i-1];
        if(i == sz(g[u])-qtd-1) dp[u][1] = ans;
        if(i == sz(g[u])-qtd) dp[u][0] = ans;
    }
}

std::vector<int> minimum_closure_costs(int32_t N, std::vector<int32_t> U,std::vector<int32_t> V,std::vector<int32_t> W) {
    n = N;
    vector<int> ans;
    int sumw = 0;
    for(int i = 0; i < n-1; i++) {
        int u = U[i];
        int v = V[i];
        int w = W[i];
        sumw+= w;
        g[u].pb(i);
        g[v].pb(i);
        gesp[u].pb(mp(v,w));
        gesp[v].pb(mp(u,w));
    }

    ans.pb(sumw);
    for(int k = 1; k <= n-1; k++) {
        dfs(0,k,-1);
        ans.pb(dp[0][0]);
    }

    return ans;
    



    // for(int i = 0; i < n; i++) {
    //     gr[g[i].size()].pb(i);
    // }

    // vector<int> esp;
    // vector<int> ans;
    // for(int i = 0; i < n; i++) {
    //     int ans1 = 0;
    //     for(auto u : gr[i]) {
    //         esp.pb(u);
    //         atv[u] = 1;
    //         for(auto id : g[u]) {
    //             int v = u^U[id]^V[id];
    //             int w = W[id];
    //             if(atv[v]) {
    //                 gesp[u].pb(mp(v,w));
    //                 gesp[v].pb(mp(u,w));
    //             }
    //         }
    //     }
    //     for(auto v : esp) {
    //         if(mark[v] != i+1) dfs(v,i,-1);
    //     }
    // }

    return std::vector<long long>(N, 0);
}

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