제출 #981361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981361		sleepntsheep	도로 폐쇄 (APIO21_roads)	C++14	24 / 100	319 ms	4956 KiB

roads

long long dir(long long x){return x<0?-1:x>0?1:0;}
int max(int i,int j){return i>j?i:j;}

#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], sum;
    int ao, i;

    sum = 0;
    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_tight[v] - dp_loose[v]);
        sum += w + dp_tight[v];
    }

    /* for tight : can have at most k alive children
     * for loose : can have at most k-1 alive children
     *
     */

    qsort(aa, ao, sizeof*aa, ij);

    dp_tight[u] = sum;
    for (i = 0; i < ao && i < k && aa[i] <= 0; ++i)
        dp_tight[u] += aa[i];

    dp_loose[u] = sum;
    for (i = 0; i < ao && i < k - 1 && aa[i] <= 0; ++i)
        dp_loose[u] += aa[i];
}

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_tight[0];

    return ans;
}

• 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