| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 980576 | vjudge1 | Road Closures (APIO21_roads) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++){
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;
}
int main(){
int n;
cin >> n;
}