Submission #980404

#	Time	Username	Problem	Language	Result	Execution time	Memory
980404		nnin	Road Closures (APIO21_roads)	C++14	100 / 100	263 ms	62160 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
using ll = long long;

vector<pii> adj[100005], cur[100005];
vector<int> deg[100005];
ll dp[100005][2];
bool vis[100005];

struct segTree {
  int n;
  vector<ll> sum, val;
  vector<int> ct;

  void update(int i, int l, int r, int x, int v) {
    if(l==r) {
      sum[i] += v*val[l];
      ct[i] += v;
      return;
    }
    int m = (l+r)/2;
    if(x<=m) update(i*2+1, l, m, x, v);
    else update(i*2+2, m+1, r, x, v);
    sum[i] = sum[i*2+1]+sum[i*2+2];
    ct[i] = ct[i*2+1]+ct[i*2+2];
  }
  void update(int w, int v) {
    int it = lower_bound(val.begin(), val.end(), w)-val.begin();
    update(0, 0, n-1, it, v);
  }

  void build(vector<ll> &v) {
    val = v;
    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end())-val.begin());
    n = val.size();
    sum.resize(4*n+1, 0);
    ct.resize(4*n+1, 0);
    for(int vv:v) update(vv, 1);
  }

  int find(int i, int l, int r, int x) {
    if(ct[i]<x) return 2e9;
    if(l==r) {
      if(ct[i]>=x) return val[l];
      return 2e9;
    }
    int m = (l+r)/2;
    if(ct[i*2+1]>=x) return find(i*2+1, l, m, x);
    else return find(i*2+2, m+1, r, x-ct[i*2+1]);
  }
  int find(int x) {
    return find(0, 0, n-1, x);
  }

  ll findsum(int i, int l, int r, int x) {
    if(ct[i]<=x) return sum[i];
    if(x==0) return 0;
    if(l==r) {
      if(ct[i]>=x) return x*val[l];
      return sum[i];
    }
    int m = (l+r)/2;
    if(ct[i*2+1]>=x) return findsum(i*2+1, l, m, x);
    else return findsum(i*2+1, l, m, x)+findsum(i*2+2, m+1, r, x-ct[i*2+1]);
  }
  ll findsum(int x) {
    return findsum(0, 0, n-1, x);
  }
};
vector<segTree> t;

void dfs(int u, int p, int wp, int mx) {
  vis[u] = 1;
  dp[u][0] = 0;
  dp[u][1] = wp;
  for(int j=0;j<2;j++) {
    int ct = adj[u].size()-mx-j;
    vector<ll> add;
    for(auto [v, w]:cur[u]) {
      if(v==p) continue;
      if(!vis[v]) dfs(v, u, w, mx);
      dp[u][j] += min(dp[v][0], dp[v][1]);
      if(dp[v][1]<dp[v][0]) ct--;
      else add.push_back(dp[v][1]-dp[v][0]);
    }
    if(ct<=0) continue;
    sort(add.begin(), add.end());
    for(int i=0; i<add.size() && ct; i++) {
      if(add[i]<t[u].find(ct)) {
        dp[u][j] += add[i];
        ct--;
      } else {
        break;
      }
    }
    if(ct) dp[u][j] += t[u].findsum(ct);
  }
}

vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
  for(int i=0;i<n-1;i++) {
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }
  for(int i=0;i<n;i++) {
    deg[adj[i].size()-1].push_back(i);
  }
  vector<int> nodes;
  vector<long long> ans(n, 0);
  t.resize(n);
  for(int i=0;i<n;i++) {
    vector<ll> val;
    for(auto [v, w]:adj[i]) val.push_back((ll)w);
    t[i].build(val);
  }
  for(int i=n-1;i>=0;i--) {
    for(int u:deg[i]) {
      for(auto [v, w]:adj[u]) {
        cur[v].push_back({u, w});
        t[v].update(w, -1);
      }
      nodes.push_back(u);
    }
    for(int u:nodes) {
      if(vis[u]) continue;
      dfs(u, -1, 0, i);
      ans[i] += dp[u][0];
    }
    for(int u:nodes) {
      vis[u] = 0;
    }
  }
  return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int, int)':
roads.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto [v, w]:cur[u]) {
      |              ^
roads.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0; i<add.size() && ct; i++) {
      |                  ~^~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:118:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for(auto [v, w]:adj[i]) val.push_back((ll)w);
      |              ^
roads.cpp:123:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |       for(auto [v, w]:adj[u]) {
      |                ^

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