제출 #1195034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195034		dzuizz	Road Closures (APIO21_roads)	C++20	7 / 100	32 ms	10824 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
    long long 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;
}

vector<long long> brute_force(int n,vector<int>U,vector<int>V,vector<int>W){
  vector<long long> ret(n,0); ret[1]=3e18;
  bool v[n-1];
  for(long long msk=0;msk<(1<<(n-1));++msk){
    for(int i=0;i<n;++i) v[i]=msk>>i&1;
    bool f=0;
    for(int i=1;i<n-1&&!f;++i){
      if(v[i]&&v[i-1]) f=1;
    }
    if(f) continue;
    long long res=0;
    for(int i=0;i<n-1;++i) if(!v[i]){
      res+=W[i];
    }
    ret[1]=min(ret[1],res);
  }
  for(int i=0;i<n-1;++i) ret[0]+=W[i];
  return ret;
}

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