Submission #1195019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195019		dzuizz	Road Closures (APIO21_roads)	C++20	0 / 100	37 ms	10056 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);

  vector<long long> ret(n,0);

  {  // Subtask 2 - Line graph
    int dp[n-1][2];  // 0-notake, 1-take
    dp[0][0]=W[0];
    dp[0][1]=0;
    for(int i=1;i<n-1;++i){
      dp[i][0]=min(dp[i-1][0],dp[i-1][1])+W[i];
      dp[i][1]=dp[i-1][0];
    }
    ret[1]=min(dp[n-2][0],dp[n-2][1]);
    for(int i=0;i<n-1;++i) ret[0]+=W[i];
  }

  /*
  {  // Subtask 1 - Star graph
    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: 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