Submission #1195002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195002		dzuizz	Road Closures (APIO21_roads)	C++20	5 / 100	41 ms	10092 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5;
int n;
vector<pair<int,int>> g[N];

pair<int,int> pa[N];
int s[N],_s;
void dfs(int i){
  for(auto&[w,x]:g[i]) if(x!=pa[i].second){
    pa[x]={w,i};
    dfs(x);
  }
  s[_s++]=i;
}
std::vector<long long> minimum_closure_costs(int _n,vector<int> U,vector<int> V,vector<int> W){
  n=_n;
  for(int i=0;i<n-1;++i){
    g[U[i]].emplace_back(W[i],V[i]);
    g[V[i]].emplace_back(W[i],U[i]);
  }
  //pa[0]={0,0}; dfs(0);

  // Subtask 1 - Star graph
  std::vector<long long> ret(n);
  ret[n-1]=0;
  sort(W.begin(),W.end(),greater<int>());
  for(int i=n-2;i>=0;--i){
    ret[i]=ret[i+1]+W[i];
  }
  return ret;
}

• Subtask 1: 5 / 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