Submission #1003543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003543		AdamGS	Road Closures (APIO21_roads)	C++17	14 / 100	2072 ms	36148 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) {
  int d=min(k, (int)V[x].size())+1;
  vector<ll>A(d+1, -INF), B(d+1, -INF);
  A[0]=B[1]=0;
  for(auto i : V[x]) if(i.st!=o) {
    DFS(i.st, x, k);
    for(int j=d-1; j>=0; --j) {
      A[j]+=dp[i.st][0];
      if(j) A[j]=max(A[j], A[j-1]+dp[i.st][1]);
      B[j]+=dp[i.st][0];
      if(j) B[j]=max(B[j], B[j-1]+dp[i.st][1]);
    }
  }
  for(auto i : V[x]) if(i.st==o) {
    rep(j, B.size()) B[j]+=i.nd;
  }
  rep(i, A.size()) dp[x][0]=max(dp[x][0], A[i]);
  rep(i, B.size()) dp[x][1]=max(dp[x][1], B[i]);
}
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:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
roads.cpp:28:5: note: in expansion of macro 'rep'
   28 |     rep(j, B.size()) B[j]+=i.nd;
      |     ^~~
roads.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
roads.cpp:30:3: note: in expansion of macro 'rep'
   30 |   rep(i, A.size()) dp[x][0]=max(dp[x][0], A[i]);
      |   ^~~
roads.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
roads.cpp:31:3: note: in expansion of macro 'rep'
   31 |   rep(i, B.size()) dp[x][1]=max(dp[x][1], B[i]);
      |   ^~~

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