Submission #718658

#	Time	Username	Problem	Language	Result	Execution time	Memory
718658		lam	Road Closures (APIO21_roads)	C++14	24 / 100	2086 ms	21968 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,k;
ll dp[2][maxn];
vector <ii> adj[maxn];

void dfs(int x, int p)
{
    ll sum = 0LL;
    vector <ll> tmp;
    for (ii i:adj[x])
        if (i.ff!=p)
    {
        dfs(i.ff,x);
        sum += dp[0][i.ff];
//        cerr<<x<<" -> "<<i.ff<<endl;
        tmp.push_back(dp[1][i.ff]+i.ss-dp[0][i.ff]);
    }
    sort(tmp.begin(),tmp.end(),greater<ll>());
//    cerr<<x<<' '<<sum<<" : ";
//    for (ll i:tmp) cerr<<i<<' '; cerr<<endl;
    vector <ll> tmp2 = tmp;
    dp[0][x] = sum;
    while (!tmp.empty()&&(tmp.size()+(p!=-1)>k||(tmp.back() < 0)))
    {
        dp[0][x] += tmp.back();
        tmp.pop_back();
    }
    dp[1][x] = sum;
    while (!tmp2.empty()&&(tmp2.size()+(p!=-1)>k+1||(tmp2.back()<0)))
    {
        dp[1][x] += tmp2.back();
        tmp2.pop_back();
    }
//    cerr<<x<<' '<<dp[0][x]<<' '<<dp[1][x]<<" !! "<<endl;
}

vector <ll> minimum_closure_costs(int N, vector <int>U, vector<int>V, vector<int>W)
{
    n=N;
    for (int i=0; i<n; i++) adj[i].clear();
    for (int i=0; i<n-1; i++)
    {
        int u=U[i]; int v=V[i];
        int w=W[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    vector <ll> ans;
    for (int kk=0; kk<n; kk++)
    {
        k=kk;
        dfs(0,-1);
        ans.push_back(dp[0][0]);
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:30:45: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     while (!tmp.empty()&&(tmp.size()+(p!=-1)>k||(tmp.back() < 0)))
      |                           ~~~~~~~~~~~~~~~~~~^~
roads.cpp:36:47: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     while (!tmp2.empty()&&(tmp2.size()+(p!=-1)>k+1||(tmp2.back()<0)))
      |                            ~~~~~~~~~~~~~~~~~~~^~~~

• 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