Submission #861085

#	Time	Username	Problem	Language	Result	Execution time	Memory
861085		mychecksedad	Road Closures (APIO21_roads)	C++17	24 / 100	2094 ms	24452 KiB

roads

// #include<roads.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int M = 2e5+10, K = 22;

int n;
vector<array<ll, 2>> g[M];

array<ll, 2> dfs(int v, int p, int k, ll W){
  vector<array<ll, 2>> dps;
  array<ll, 2> dp; // parent isnt cut, parent cut
  for(auto U: g[v]){
    int u = U[0]; ll w = U[1];
    if(p != u){
      dps.pb(dfs(u, v, k, w));
    }
  }

  dp[0] = 0, dp[1] = W;

  sort(all(dps), [&](const array<ll, 2> &a, const array<ll, 2> &b){
    return (a[1] - a[0]) < (b[1] - b[0]);
  });

  int _k = int(g[v].size()) - k;

  for(int i = 0; i < dps.size(); ++i){
    if(dps[i][1] - dps[i][0] < 0){
      dp[0] += dps[i][1];
      dp[1] += dps[i][1];
    }else if(i < _k){
      dp[0] += dps[i][1];
      if(i < _k - 1){
        dp[1] += dps[i][1];
      }else{
        dp[1] += dps[i][0];
      }
    }else{
      dp[0] += dps[i][0];
      dp[1] += dps[i][0];
    }
  }

  // cout << v << ' ' << k << ' ' <<  dp[0] << ' ' << dp[1] << '\n';

  return dp;
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W){
  n = N;
  for(int i = 0; i < n-1; ++i){
    g[U[i]].pb({V[i], W[i]});
    g[V[i]].pb({U[i], W[i]});
  }
  vector<ll> ans;
  for(int i = 1; i <= n; ++i)
    ans.pb(dfs(0, 0, i-1, 1ll*1e15)[0]);

  return ans;
}

Compilation message (stderr)

roads.cpp: In function 'std::array<long long int, 2> dfs(int, int, int, long long int)':
roads.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int i = 0; i < dps.size(); ++i){
      |                  ~~^~~~~~~~~~~~

• 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