Submission #824601

#	Time	Username	Problem	Language	Result	Execution time	Memory
824601		Hanksburger	Road Closures (APIO21_roads)	C++17	21 / 100	2070 ms	36280 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > adj[100005];
long long dp[100005][2], deg[100005], limit;
vector<long long> ans;
void dfs(long long u, long long p, long long x)
{
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i].first, w=adj[u][i].second;
        if (v==p)
            continue;
        dfs(v, u, w);
    }
    vector<long long> vec, tmp;
    vec.push_back(0);
    for (long long i=1; i<=limit; i++)
        vec.push_back(1e18);
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i].first, w=adj[u][i].second;
        if (v==p)
            continue;
        tmp.push_back(vec[0]+dp[v][0]);
        for (int j=1; j<=limit; j++)
            tmp.push_back(min(vec[j]+dp[v][0], vec[j-1]+dp[v][1]));
        vec=tmp;
        tmp.clear();
    }
    long long mn=1e18;
    for (long long i=0; i<limit; i++)
        mn=min(mn, vec[i]);
    dp[u][0]=min(mn, vec[limit])+x;
    dp[u][1]=mn;
}
vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w)
{
    for (long long i=0; i<n-1; i++)
    {
        adj[u[i]].push_back({v[i], w[i]});
        adj[v[i]].push_back({u[i], w[i]});
        deg[u[i]]++, deg[v[i]]++;
    }
    long long mx=0;
    for (long long i=0; i<n; i++)
        mx=max(mx, deg[i]);
    for (long long i=0; i<mx; i++)
    {
        limit=i;
        dfs(0, 0, 0);
        ans.push_back(dp[0][0]);
    }
    for (long long i=mx; i<n; i++)
        ans.push_back(0);
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int, long long int)':
roads.cpp:9:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~
roads.cpp:20:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~
roads.cpp:22:38: warning: unused variable 'w' [-Wunused-variable]
   22 |         long long v=adj[u][i].first, w=adj[u][i].second;
      |                                      ^

• Subtask 1: 0 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22