| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 981357 | sleepntsheep | 도로 폐쇄 (APIO21_roads) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
long long dir(long long x){return x<0?-1:x>0?1:0;}
#define assert(x) if(!(x))__builtin_trap()
#include "roads.h"
#include<stdlib.h>
#include <vector>
#define NN 2000
#define MM (2*NN)
int head[NN], nxt[MM], vv[MM], ww[MM];
void link(int u,int v,int w)
{
static int i=1;
nxt[i]=head[u];
vv[i]=v;
ww[i]=w;
head[u]=i++;
}
long long dp_loose[NN], dp_tight[NN];
typedef struct { long long a, b; } ab;
int abdec(ab a, ab b) { if(a.a^b.a)return -dir(a.a-b.a);return -dir(a.b-b.b);}
int ij(const void*ii,const void*jj){return -dir(*(const long long*)ii-*(const long long*)jj);}
void dfs(int u,int p,int k)
{
for(int j=head[u];j;j=nxt[j])if(vv[j]-p)
dfs(vv[j], u, k);
static long long aa[NN];
long long sum = 0;
int ao = 0;
for(int j=head[u];j;j=nxt[j])if(vv[j]-p)
{
int v=vv[j],w=ww[j];
aa[ao] = w + dp_loose[v] - dp_tight[v];
if (aa[ao] >= 0) ++ao;
sum += dp_tight[v];
}
/* for tight : can have at most k loose children
*
*/
qsort(aa, ao, sizeof*aa, ij);
int i;
for(i=k;i<ao;++i)
sum += aa[i];
dp_loose[u] = sum;
if(k-1>=0&&k-1<ao)
sum += aa[k-1];
dp_tight[u] = sum;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
if(N>2000)__builtin_unreachable();
for(int i=0;i<N-1;++i)link(U[i],V[i],W[i]),link(V[i],U[i],W[i]);
std::vector<long long> ans(N);
for(int k=0;k<N;++k)
dfs(0, 0, k), ans[k] = dp[0][1];
return ans;
}