Submission #980573

#	Time	Username	Problem	Language	Result	Execution time	Memory
980573		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	48 ms	41064 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[k].size());
  if(k != 1) dl--;
  dl -= k;
  for(int i = 0; i < dl; i++){
    dp[p] += d[p][i].first;
    us[d[p][i].second] = 1;
  }
  if(dl >= 0 && k != 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;
    }
  }
}
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; i++){
    U[i]++;
    W[i]++;
    g[U[i]].push_back({V[i], W[i]});
    g[V[i]].push_back({U[i], 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;
}

• 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