| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 711427 | irmuun | 도로 폐쇄 (APIO21_roads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define PI 3.1415926535897932384626433
#define all(s) s.begin(),s.end()
const ll mod=1000000007,mod1=998244353,INF=1e18,MAX=1e9;
vector<ll> minimum_closure_costs(int n,vector<int>U,vector<int>V,vector<int>W){
int cnt=0;
bool ok=true;
for(ll i=0;i<n-1;i++){
if(U[i]==0){
cnt++;
}
if(U[i]!=i||V[i]!=i+1){
ok=false;
}
}
if(cnt==n-1){
sort(all(W));
ll cur=0;
for(ll i=0;i<n;i++){
cur+=W[i];
}
vector<ll>ans;
for(ll i=n-1;i>=0;i--){
cur-=W[i];
ans.pb(cur);
}
return ans;
}
if(ok==true){
vector<ll>ans(n,0);
ll cur=0;
for(int i=0;i<n-1;i++){
cur+=W[i];
}
ans[0]=cur;
ll dp[n+5];
dp[0]=0;
dp[1]=W[0];
for(int i=2;i<n;i++){
dp[i]=min(dp[i-1],dp[i-2])+W[i-1];
}
ans[1]=min(dp[n-1],dp[n-2]);
return ans;
}
ll dp[n+5][2];
vector<pair<ll,ll>>dv[n+5];
for(ll i=0;i<n-1;i++){
dv[U[i]].pb({V[i],W[i]});
dv[V[i]].pb({U[i],W[i]});
}
ll curK;
function <void(ll,ll)> dfs=[&](ll u,ll p){
vector<ll>vec;
dp[u][0]=0;
dp[u][1]=0;
for(auto [x,y]:dv[u]){
if(x!=p){
dfs(x,u);
dp[x][0]+=y;
vec.pb(x);
}
}
sort(all(vec),[&](ll a,ll b){
return dp[a][1]-dp[a][0]<dp[b][1]-dp[b][0];
});
dp[u][0]=0;
dp[u][1]=0;
for(ll x=0;auto ver:vec){
if(i<curK){
dp[ver][0]+=min(dp[ver][0],dp[ver][1]);
}
else{
dp[ver][0]+=dp[ver][0];
}
if(i<curK-1){
dp[u][1]+=min(dp[ver][0],dp[ver][1]);
}
else{
dp[u][1]+=dp[ver][0];
}
}
};
vector<ll>ans(n,0);
for(ll k=0;k<n;k++){
curK=k;
dfs(0,-1);
ans.pb(min(dp[0][0],dp[0][1]));
}
return ans;
}