Submission #743495

#	Time	Username	Problem	Language	Result	Execution time	Memory
743495		onebit1024	Road Closures (APIO21_roads)	C++17	0 / 100	36 ms	4424 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<int>c = {0,0};
  for(int i = 0;i<n-1;++i)c.pb(W[i]);
  vector<int>dp(n+1);
  for(int i = 2;i<=n;++i)dp[i] = max(dp[i-1],dp[i-2]+c[i]);
  int tot = accumulate(all(W),0ll);

  vector<ll>res = {tot,tot-dp[n]};
  if(n==2)return {tot,0};
  for(int 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:75: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]
   75 |       for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
      |                             ~^~~~~~~~~~~
roads.cpp:78: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]
   78 |       for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
      |                             ~^~~~~~~~~~~
roads.cpp:84: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]
   84 |     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