Submission #980638

#	Time	Username	Problem	Language	Result	Execution time	Memory
980638		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	2090 ms	32144 KiB

roads

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#include "roads.h"
#define ll long long

using namespace std;
vector<pair<int, ll>> g[200005]; 
vector<pair<ll, int>> d[200005];
ll dop[200005], dp[200005];
bool us[200005];
void dfs(int p, int last, int k){
  for(auto to : g[p]){
    if(to.first == last) continue;
    dfs(to.first, p, k); 
    dp[p] += dp[to.first];
    d[p].push_back({to.second - dop[to.first], to.first});
  }
  sort(d[p].begin(), d[p].end());
  int dl = int(g[p].size());
  dl -= k;
  if(p != 1) dl--;
  int ind = 0;
  while(ind < d[p].size() && d[p][ind].first <= 0){
    dp[p] += d[p][ind].first;
    us[d[p][ind].second] = 1;
    ind++;
    dl--;
  }
  int x = min(int(d[p].size()), ind + dl);
  for(int i = ind; i < x; i++){
    dp[p] += d[p][i].first;
    us[d[p][i].second] = 1;
    dl--;
    ind++;
  }
  if(dl >= 0 && p != 1){
    ll mn = 2e9;
    for(auto to : g[p]){
      if(to.first == last) continue;
      if(!us[to.first])
        mn = min(mn, to.second);
    }
    if(mn != 2e9){
      dp[p] += mn;
      dop[p] = mn;
    }
  }
  // if(k == 1 && p == 3) cout << dop[p] << "\n";
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  vector<ll> ans;
  ll sum = 0;
  for(int i = 0; i < N - 1; i++){
    g[U[i] + 1].push_back({V[i] + 1, W[i]});
    g[V[i] + 1].push_back({U[i] + 1, W[i]});
    sum += W[i];
  }
  for(int i = 0; i < N; i++){
    if(i == 0){
      ans.push_back(sum);
      continue;
    }
    for(int j = 1; j <= N; j++){
      dop[j] = dp[j] = 0;
      us[j] = 0;
      d[j].clear();
    }
    dfs(1, 0, i);
    ans.push_back(dp[1]);
  }
  return ans;
}
// vector<int> a, b, c;
// int main(){
//   int n;
//   cin >> n;
//   for(int i = 1; i < n; i++){
//     int x, y, z;
//     cin >> x >> y >> z;
//     a.push_back(x);
//     b.push_back(y);
//     c.push_back(z);
//   }
//   vector<ll> ans = minimum_closure_costs(n, a, b, c);
//   for(int to : ans) cout << to << " ";

// }

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   while(ind < d[p].size() && d[p][ind].first <= 0){
      |         ~~~~^~~~~~~~~~~~~

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