Submission #737442

#	Time	Username	Problem	Language	Result	Execution time	Memory
737442		keisuke6	Road Closures (APIO21_roads)	C++14	14 / 100	2079 ms	20468 KiB

roads

#include "roads.h"

#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
vector<vector<pair<int,int>>> G(100100);
map<pair<int,bool>,ll> m;
int bor = 0;
ll f(int x, int par, bool p){
  if(m.count({x,p})) return m[{x,p}];
  int ed = p;
  vector<ll> S = {};
  ll ans = 0;
  for(auto y:G[x]){
    int u,w;
    tie(u,w) = y;
    if(par == u) continue;
    ans += f(u,x,false)+w;
    S.push_back(f(u,x,true)-(f(u,x,false)+w));
  }
  sort(S.begin(),S.end());
  int now = 0;
  if(ed > bor) return 1e9;
  while(ed < bor && now != S.size() && S[now] < 0){
    ed++;
    ans += S[now];
    now++;
  }
  return m[{x,p}] = ans;
}
std::vector<ll> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  for(int i=0;i<W.size();i++){
    G[U[i]].push_back({V[i],W[i]});
    G[V[i]].push_back({U[i],W[i]});
  }
  vector<ll> A = {};
  for(int i=0;i<N;i++){
    bor = i;
    m.clear();
    A.push_back(f(0,-1,false));
  }
  return A;
}

Compilation message (stderr)

roads.cpp: In function 'll f(int, int, bool)':
roads.cpp:26:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   while(ed < bor && now != S.size() && S[now] < 0){
      |                     ~~~~^~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<W.size();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