Submission #1037880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037880		juicy	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	396 ms	39076 KiB

designated_cities

// https://codeforces.com/blog/entry/66022?#comment-501121

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, q;
int sz[N], c[N];
bool del[N];
long long dp[N], f[N], ans[N];
vector<array<int, 2>> g[N];

void pre_dfs(int u, int p) {
  for (auto [v, w] : g[u]) {
    if (v ^ p) {
      pre_dfs(v, u);
      dp[u] += dp[v] + w;  
    } else {
      c[u] = w;
    }
  }
}

void reroot(int u, int p) {
  for (auto [v, w] : g[u]) {
    if (v != p) {
      f[v] = f[u] + dp[u] - dp[v] - w + c[v];
      reroot(v, u);
    }
  }
}

long long get(int u, int p, vector<long long> &costs) {
  long long mx = 0;
  for (auto [v, w] : g[u]) {
    if (!del[v] && v != p) {
      auto nxt = get(v, u, costs) + w;
      if (nxt > mx) {
        swap(nxt, mx);
      }
      if (nxt) {
        costs.push_back(nxt);
      }
    }
  }
  return mx;
}

void dfs(int u, int p) {
  sz[u] = 1;
  for (auto [v, w] : g[u]) {
    if (v != p && !del[v]) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int findCen(int u, int p, int tot) {
  for (auto [v, w] : g[u]) {
    if (v != p && !del[v] && sz[v] * 2 > tot) {
      return findCen(v, u, tot);
    }
  }
  return u;
}

void cd(int u) {
  dfs(u, u);
  u = findCen(u, u, sz[u]);
  del[u] = 1;
  vector<pair<long long, int>> cands;
  for (auto [v, w] : g[u]) {
    if (!del[v]) {
      vector<long long> costs;
      long long mx = get(v, u, costs);
      costs.push_back(mx + w);
      for (auto x : costs) {
        cands.push_back({x, v});
      }
    }
  }
  sort(cands.rbegin(), cands.rend());
  long long tot = dp[u] + f[u], sum = 0;
  ans[1] = min(ans[1], tot);
  for (int i = 0; i < cands.size(); ++i) {
    sum += cands[i].first;
    ans[i + 2] = min(ans[i + 2], tot - sum);
  }
  int j = -1;
  for (int i = 1; i < cands.size(); ++i) {
    if (cands[i].second != cands[0].second) {
      j = i;
      break;
    }
  }
  if (~j) {
    long long sum = cands[j].first;
    for (int i = 0, sz = 1; i < cands.size(); ++i) {
      if (i != j) {
        sum += cands[i].first, ++sz;
        ans[sz] = min(ans[sz], tot - sum);
      }
    } 
  }
  for (auto [v, w] : g[u]) {
    if (!del[v]) {
      cd(v);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v, c, d; cin >> u >> v >> c >> d;
    g[u].push_back({v, c});
    g[v].push_back({u, d});
  }
  pre_dfs(1, 1);
  reroot(1, 1);
  memset(ans, 0x3f, sizeof(ans));
  cd(1);
  for (int i = 2; i <= n; ++i) {
    ans[i] = min(ans[i], ans[i - 1]);
  }
  cin >> q;
  while (q--) {
    int e; cin >> e;
    cout << ans[e] << "\n";
  }
  return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void cd(int)':
designated_cities.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i = 0; i < cands.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~
designated_cities.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i = 1; i < cands.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~
designated_cities.cpp:107:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0, sz = 1; i < cands.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44