제출 #1186381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186381		Aviansh	도로 폐쇄 (APIO21_roads)	C++20	5 / 100	31 ms	3888 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

using namespace std;
const int N = 2005;
void dfs(int st, vector<array<int,2>>g[], int p, long long dp[][2][N]){
    int n = N;
    int parw = 0;
    for(array<int,2>e:g[st]){
        if(e[0]==p){
            parw=e[1];
            continue;
        }
        dfs(e[0],g,st,dp);
    }
    for(int i = 0;i<n;i++){
        //dp[st][0][i] to be found
        vector<long long>deltas;
        for(array<int,2>e:g[st]){
            if(e[0]==p){
                continue;
            }
            dp[st][0][i]+=dp[e[0]][0][i];
            deltas.push_back(dp[e[0]][1][i]-dp[e[0]][0][i]);
        }
        sort(deltas.begin(),deltas.end());
        reverse(deltas.begin(),deltas.end());
        dp[st][1][i]=dp[st][0][i];
        for(int ind = 0;ind<min(i,(int)deltas.size());ind++){
            dp[st][0][i]+=max(0LL,deltas[ind]);
        }
        for(int ind = 0;ind<min(i-1,(int)deltas.size());ind++){
            dp[st][1][i]+=max(0LL,deltas[ind]);
        }
        if(i){
            dp[st][1][i]+=parw;
        }
    }
}

vector<long long> minimum_closure_costs(int n, vector<int> u,vector<int> v,vector<int> w) {
    //star case:
    vector<long long>fin;

    sort(w.begin(),w.end());
    fin.push_back(w[0]);
    for(int i = 1;i<n-1;i++){
        fin.push_back(fin.back()+w[i]);
    }
    reverse(fin.begin(),fin.end());
    fin.push_back(0);
    return fin;

    vector<array<int,2>>g[n];
    long long tot = 0;
    for(int i = 0;i<n-1;i++){
        g[u[i]].push_back({v[i],w[i]});
        tot+=w[i];
        g[v[i]].push_back({u[i],w[i]});
    }
    long long dp[n][2][N];
    for(int i = 0;i<n;i++){
        fill(dp[i][0],dp[i][0]+N,0);
        fill(dp[i][1],dp[i][1]+N,0);
    }
    dfs(0,g,-1,dp);
    vector<long long>ans;
    for(int i = 0;i<n;i++){
        ans.push_back(tot-dp[0][0][i]);
    }
    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