Submission #981335

#	Time	Username	Problem	Language	Result	Execution time	Memory
981335		sleepntsheep	Road Closures (APIO21_roads)	C++11	0 / 100	442 ms	4956 KiB

roads

long long dir(long long x){return x<0?-1:x>0?1:0;}

#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[NN][2];

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 abdec(*(const ab*)ii,*(const ab*)jj);}

void dfs(int u,int p,int k)
{
    static ab aa[NN];

    for(int j=head[u];j;j=nxt[j])if(vv[j]-p)
        dfs(vv[j], u, k);

    long long sum = 0;
    int ao = 0;
    for(int j=head[u];j;j=nxt[j])if(vv[j]-p)
    {
        /*
         * not cut - use dp[to][0]
         * cut - use dp[to][1] + ww[j]
         * profit - dp[to][1] + ww[j] - dp[to][0]
         * */
        
        aa[ao] = (ab){ww[j] + dp[vv[j]][1] - dp[vv[j]][0], ww[j] + dp[vv[j]][0]};
        ++ao;
        sum += dp[vv[j]][0];
    }

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

    int i;
    for(i=k;i<ao;++i)
        sum += aa[i].a;
    dp[u][1] = sum;
    if(k-1>=0&&k-1<ao)
        sum += aa[k-1].a;
    dp[u][0] = sum;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
        std::vector<int> V,
        std::vector<int> W) {
    for(int i=0;i<N-1;++i)link(U[i],V[i],W[i]),link(V[i],U[i],W[i]);
    auto ans = std::vector<long long>(N, 0);

    for(int k=0;k<N;++k)
        dfs(0, 0, k), ans[k] = dp[0][1];


    return ans;
}

• Subtask 1: 0 / 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