Submission #902349

#	Time	Username	Problem	Language	Result	Execution time	Memory
902349		efedmrlr	도로 폐쇄 (APIO21_roads)	C++17	24 / 100	2094 ms	30664 KiB

roads

#include "roads.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)



void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int M = 1e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q,k;

vector<int> deg(M, 0), p(M, 0);
vector<vector<array<lli,2> > > adj(M, vector<array<lli,2> >());
vector<lli> dp[2];
void dfs(int node, int par) {
  p[node] = par;
  deg[node] = (int)adj[node].size();
  for(auto itr = adj[node].begin(); itr!=adj[node].end();) {
    auto &c = *itr;
    if(c[0] == par) {
      itr = adj[node].erase(itr);
      continue;
    }
    dfs(c[0], node);
    itr++;
  }

}

void f(int node, int par) {
  // cout<<"node:"<<node<<" par:"<<par<<endl;
  if(adj[node].empty() && node) {
    dp[0][node] = 0; dp[1][node] = 0;
    // cout<<"node out:"<<node<<" par:"<<par<<endl;
    return;
  } 
  for(auto c : adj[node]) {
    if(c[0] == par) continue;
    f(c[0], node);
  }
  vector<lli> A1, A2;
  vector<array<lli,2> > srt;
  lli cost = 0;
  int left = max(0, deg[node] - k);
  for(int i = 0; i<adj[node].size(); i++) {
    lli x = dp[1][adj[node][i][0]] + adj[node][i][1];
    lli y = dp[0][adj[node][i][0]];
    srt.pb({x - y, (lli)A1.size()});
    A1.pb(x); A2.pb(y);
  }
  sort(srt.begin(), srt.end());
  for(int i = 0; i<left; i++) {
    cost += A1[srt[i][1]];
  }
  for(int i = left; i<A1.size(); i++) {
    cost += min(A1[srt[i][1]], A2[srt[i][1]]);
  }
  dp[0][node] = cost;
  left--;
  if(left >= 0) dp[1][node] = cost - A1[srt[left][1]] + min(A1[srt[left][1]], A2[srt[left][1]]);
  else dp[1][node] = cost;
  // cout<<"dp0:"<<dp[0][node]<<" dp1:"<<dp[1][node]<<"\n";

  // cout<<"node out:"<<node<<" par:"<<par<<endl;
}

lli solve() {
  dp[0].assign(n + 3, 0); dp[1].assign(n + 3, 0);
  f(0, 0);
  return dp[0][0];
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
  std::vector<int> V,
  std::vector<int> W) {
    n = N;
    lli sum = 0ll;
    for(int i = 0; i<n - 1; i++) {
      adj[U[i]].pb({V[i], W[i]});
      adj[V[i]].pb({U[i], W[i]});
      sum += W[i]; 
    }
    vector<lli> ans(n);
    ans[0] = sum;
    dfs(0, 0);
    for(int i = 1; i<n; i++) {
      k = i;
      ans[i] = solve();
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void f(int, int)':
roads.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i<adj[node].size(); i++) {
      |                  ~^~~~~~~~~~~~~~~~~
roads.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i = left; i<A1.size(); i++) {
      |                     ~^~~~~~~~~~

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