Submission #1003550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003550		AdamGS	Road Closures (APIO21_roads)	C++17	24 / 100	2096 ms	27048 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll dp[LIM][2], n;
void DFS(int x, int o, int k) {
  ll sum0=0;
  vector<ll>D;
  for(auto i : V[x]) if(i.st!=o) {
    DFS(i.st, x, k);
    sum0+=dp[i.st][0];
    D.pb(dp[i.st][1]-dp[i.st][0]);
  }
  sort(all(D));
  reverse(all(D));
  int d=min(k, (int)V[x].size())+1;
  while(D.size()<d-1) D.pb(-INF);
  vector<ll>P(d);
  P[0]=sum0;
  rep(i, d-1) P[i+1]=P[i]+D[i];
  rep(i, d) if(i<k) dp[x][1]=max(dp[x][1], P[i]);
  rep(i, d) dp[x][0]=max(dp[x][0], P[i]);
  for(auto i : V[x]) if(i.st==o) dp[x][1]+=i.nd;
}
ll licz(ll k) {
  rep(i, n) dp[i][0]=dp[i][1]=-INF;
  DFS(0, 0, k);
  return dp[0][0];
}
vector<ll>minimum_closure_costs(int _n, vector<int>_U, vector<int>_V, vector<int>_W) {
  n=_n;
  ll sum=0;
  rep(i, n-1) {
    V[_U[i]].pb({_V[i], _W[i]});
    V[_V[i]].pb({_U[i], _W[i]});
    sum+=_W[i];
  }
  vector<ll>wynik;
  rep(i, n) wynik.pb(sum-licz(i));
  return wynik;
}

Compilation message (stderr)

roads.cpp: In function 'void DFS(int, int, int)':
roads.cpp:25:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |   while(D.size()<d-1) D.pb(-INF);
      |         ~~~~~~~~^~~~

• 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