Submission #981359

#	Time	Username	Problem	Language	Result	Execution time	Memory
981359		sleepntsheep	Road Closures (APIO21_roads)	C++14	0 / 100	321 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];
    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_tight[v] - dp_loose[v];
        if (aa[ao] >= 0) ++ao;
        sum += dp_loose[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);

    int i;

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

    dp_loose[u] = sum;
    for (int i=max(0,k-1);i<ao;++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;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:52:9: warning: unused variable 'i' [-Wunused-variable]
   52 |     int i;
      |         ^

• 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