Submission #981524

#	Time	Username	Problem	Language	Result	Execution time	Memory
981524		Tsagana	Road Closures (APIO21_roads)	C++14	49 / 100	224 ms	60752 KiB

roads

#include "roads.h"

//OP
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define meta int M = (L + R) / 2, x = 2 * id + 1, y = x + 1

using namespace std;

bool vis[100005];
lnl  dp[100005][2];
vector<int> deg[100005];
vector<pi > adj[100005];
vector<pi > cur[100005];

struct Tree {
  int  n;
  vector<lnl> sum;
  vector<lnl> val;
  vector<int> ct;

  void update(int id, int L, int R, int k, int v) {
    if (L == R) {sum[id] += v * val[L]; ct[id] += v; return;} meta;
    (k <= M ? update(x, L, M, k, v) : update(y, M + 1, R, k, v));
    sum[id] = sum[x] + sum[y]; ct[id] = ct[x] + ct[y];
  } void update(int w, int v)
    {int it = lb(all(val), w) - val.begin(); update(0, 0, n-1, it, v);}
 
  int find(int id, int L, int R, int k) {
    if (ct[id] < k) return 2e9;
    if (L == R) {return (ct[id] >= k ? val[L] : 2e9);} meta;
    return (ct[x] >= k ? find(x, L, M, k) : find(y, M + 1, R, k - ct[x]));
  } int find(int x) {return find(0, 0, n-1, x);}
 
  lnl findsum(int id, int L, int R, int k) {
    if (ct[id] <= k) return sum[id]; if (k == 0) return 0;
    if (L == R) {return (ct[id] >= k ? k * val[L] : sum[id]);}
    meta; int S = findsum(x, L, M, k);
    return (ct[x] >= k ? S : S + findsum(y, M + 1, R, k - ct[x]));
  } lnl findsum(int x) {return findsum(0, 0, n-1, x);}

  void build(vector<lnl>& v) {
    val = v; sort(all(val)); val.resize(unique(all(val)) - val.begin());
    n = val.size(); sum.resize(4*n+1, 0); ct.resize(4*n+1, 0);
    for (int vv: v) update(vv, 1);
  }
};
vector<Tree> 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<lnl> add;
    for (auto i: cur[u]) {
      int v = i.F, w = i.S;
      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.pb(dp[v][1] - dp[v][0]);
    }
    if (ct <= 0) continue; sort(all(add));
    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<lnl> 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]].pb({V[i], W[i]});
    adj[V[i]].pb({U[i], W[i]});
  }
  for (int i = 0; i < N; i++) {deg[adj[i].size()-1].pb(i);}
  vector<int> nodes;
  vector<lnl> ans(N, 0);
  t.resize(N);
  for (int i = 0; i < N; i++) {
    vector<lnl> val;
    for (auto l: adj[i]) val.pb((lnl)l.S);
    t[i].build(val);
  }
  for (int i = N - 1; i >= 0; i--) {
    for (int u: deg[i]) {
      for (auto i: adj[u]) {
        cur[i.F].pb({u, i.S});
        t[i.F].update(i.S, -1);
      }
      nodes.pb(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;
}
//ED

Compilation message (stderr)

roads.cpp: In member function 'long long int Tree::findsum(int, int, int, int)':
roads.cpp:48:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |     if (ct[id] <= k) return sum[id]; if (k == 0) return 0;
      |     ^~
roads.cpp:48:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |     if (ct[id] <= k) return sum[id]; if (k == 0) return 0;
      |                                      ^~
roads.cpp: In function 'void dfs(int, int, int, int)':
roads.cpp:74:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |     if (ct <= 0) continue; sort(all(add));
      |     ^~
roads.cpp:74:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   74 |     if (ct <= 0) continue; sort(all(add));
      |                            ^~~~
roads.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < add.size() && ct; i++) {
      |                     ~~^~~~~~~~~~~~

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