Submission #743512

#	Time	Username	Problem	Language	Result	Execution time	Memory
743512		onebit1024	Road Closures (APIO21_roads)	C++17	5 / 100	66 ms	21960 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, vector<int> U,
                                             vector<int> V,
                                             vector<int> W) {
n = N;
  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]});
  for(auto &[w,v] : adj[0]){
    other[0].pb(w);
  }
  sort(all(other[0]));
  
  // comp(0,-1);
  // dfs(0,-1);
  vector<ll>res;
  ll sum = 0;
  for(int i = 0;i<n-1;++i)sum+=other[0][i],res.pb(sum);
  reverse(all(res));
  res.pb(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: 5 / 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