Submission #743612

#	Time	Username	Problem	Language	Result	Execution time	Memory
743612		onebit1024	Road Closures (APIO21_roads)	C++17	0 / 100	56 ms	12108 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"
 
const double PI=3.141592653589;
 
 
void __print(ll x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
 
#include <vector>
 
/*
dp[i][j][0] min cost to delete edges such that each node in the subtree of node i has atmost j active edges and the edge from (par[i],i) is still active
 
let's say node i has k edges from it(including parent), if parent is still active then we need to delete to delete k-j down edges otherwise if we are kiling parent edge then k-j-1 down edges to be deleted.
 
cost of deleting edge from u->v is min(dp[v][j][1],dp[v][j][0]+w[u,v]-jth costliest edge of v)
cost of keeping edge u->v is min(dp[v][j][0],dp[v][j][1])
 
sort by decreasing order of  keeping-deleting cost and delete the first x
 
*/
 
vector<vector<vector<ll>>>dp;
vector<vector<pair<ll,ll>>>adj;
vector<vector<ll>>other;
ll n;
vector<ll>par;
void dfs(ll u, ll p){
  for(auto &[w,v] : adj[u]){
    if(v==p)continue;
    dfs(v,u);
  }
  for(ll j = 0;j<n;++j){
    vector<pair<ll,ll>>val;
    for(auto &[w,v] : adj[u]){
      if(v==p)continue;
      val.pb({min(dp[v][j][0],dp[v][j][1]),dp[v][j][1]});
    }
    ll x = adj[u].size()-j;
    sort(all(val), [&](auto one,auto two){
      return one.first-one.second > two.first - two.second;
    });
    if(u==0){
      for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][0]+=val[i].second;
      for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
    }else if(j>0){
      for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][0]+=val[i].second;
      for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
 
    }
 
    x--;
    for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][1]+=val[i].second;
    for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][1] += val[i].first;
 
  }
}
 
void comp(ll u, ll p){
  for(auto &[w,v] : adj[u]){
    if(v==p)continue;
    par[v] = u;
    for(ll j = 0;j<n;++j)dp[v][j][1] = w;
    comp(v,u);
  }
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  n = N;
  vector<ll>c = {0};
  for(ll i = 0;i<n-1;++i)c.pb((ll)W[i]);  
  vector<vector<ll>>dp(n,vector<ll>(2));
  dp[0][1] = 1e18;
  for(ll i = 1;i<n;++i)dp[i][0] = dp[i-1][1],dp[i][1] = c[i]+min(dp[i-1][1],dp[i-1][0]);
  ll tot = 0;
  for(auto x : c)tot+=x;
  
  vector<ll>res = {tot,min(dp[n-1][0],dp[n-1][1])};
  if(n==2)res[1] = 0;
  for(ll i = 2;i<n;++i)res.pb(0);
  return res;
  // n = N;
  // dp = vector<vector<vector<ll>>>(n+1, vector<vector<ll>>(n+1,vector<ll>(2)));
  // adj.resize(n+1);
  // par.resize(n+1);
  // other.resize(n+1);
  // for(ll i = 0;i<n-1;++i)adj[U[i]].pb({W[i],V[i]}),adj[V[i]].pb({W[i],U[i]});
  // comp(0,-1);
  // for(ll i = 0;i<n;++i){
  //   for(auto &[w,v] : adj[i]){
  //     if(v==par[i])continue;
  //     other[i].pb(w);
  //   }
  //   sort(all(other[i]));
  //   sort(all(adj[i]));
  // }
  // for(ll i = 1;i<n;++i)dp[i][0][0] = 1e18;
  // comp(0,-1);
  // dfs(0,-1);
  // vector<ll>res;
  
 
  // for(ll i = 0;i<n;++i)res.pb(dp[0][i][0]);
  // return res;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int)':
roads.cpp:76:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |       for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
      |                             ~^~~~~~~~~~~
roads.cpp:79:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |       for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
      |                             ~^~~~~~~~~~~
roads.cpp:85:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][1] += val[i].first;
      |                           ~^~~~~~~~~~~

• 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