Submission #1200233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200233		rxlfd314	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	1093 ms	32624 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N;
  cin >> N;
  vt<vt<ari3>> adj(N);
  ll sum = 0;
  FOR(_, 2, N) {
    int a, b, c, d;
    cin >> a >> b >> c >> d, a--, b--;
    adj[a].push_back({b, c, d});
    adj[b].push_back({a, d, c});
    sum += c + d;
  }
  vt<ll> ans(N+1);
  /* 1 resort city */ {
    vt<ll> dp(N);
    auto dfs = [&](auto &&self, const int i, const int p) -> void {
      for (const auto &[j, c, d] : adj[i]) {
        if (j == p)
          continue;
        self(self, j, i);
        dp[i] += dp[j] + d;
      }
    };
    dfs(dfs, 0, -1);
    auto reroot = [&](auto &&self, const int i, const int p) -> void {
      ans[1] = max(ans[1], dp[i]);
      for (const auto &[j, c, d] : adj[i]) {
        if (j == p)
          continue;
        dp[i] -= dp[j] + d;
        dp[j] += dp[i] + c;
        self(self, j, i);
        dp[j] -= dp[i] + c;
        dp[i] += dp[j] + d;
      }
    };
    reroot(reroot, 0, -1);
  }
  /* >1 resort city */ {
    vt<int> szs(N), dead(N);
    auto dfs_szs = [&](auto &&self, const int i, const int p) -> void {
      szs[i] = 1;
      for (const auto &[j, c, d] : adj[i]) {
        if (dead[j] || j == p)
          continue;
        self(self, j, i);
        szs[i] += szs[j];
      }
    };
    auto centroid = [&](int i) {
      int p = -1;
      const int n = szs[i];
      bool flag = true;
      while (flag) {
        flag = false;
        for (const auto &[j, c, d] : adj[i]) {
          if (j == p || dead[j])
            continue;
          if (2 * szs[j] > n) {
            p = i;
            i = j;
            flag = true;
            break;
          }
        }
      }
      return i;
    };
    vt<int> parent(N), best(N), nodes;
    vt<ll> depth(N), subtree(N);
    auto dfs_par = [&](auto &&self, const int i, const int p) -> ll {
      parent[i] = p;
      best[i] = i;
      subtree[i] = 0;
      nodes.push_back(i);
      for (const auto &[j, c, d] : adj[i]) {
        if (dead[j] || j == p)
          continue;
        depth[j] = depth[i] + c;
        subtree[i] += self(self, j, i) + d;
        if (depth[best[i]] < depth[best[j]])
          best[i] = best[j];
      }
      return subtree[i];
    };
    vt<int> seen(N);
    auto decomp = [&](auto &&self, const int root, const ll add) -> void {
      dfs_szs(dfs_szs, root, -1);
      const int cent = centroid(root);
      depth[cent] = 0;
      const ll have = dfs_par(dfs_par, cent, -1);
      if (size(nodes) == 1)
        return;
      sort(all(adj[cent]), [&](const ari3 &a, const ari3 &b) {
        return depth[best[a[0]]] > depth[best[b[0]]];    
      });
      priority_queue<pair<ll, int>> pq;
      auto yeet = [&](int i) {
        for (; i >= 0 && !seen[i]; i = parent[i]) {
          seen[i] = 1;
          for (const auto &[j, c, d] : adj[i])
            if (!seen[j] && !dead[j] && j != parent[i])
              pq.push({depth[best[j]] - depth[i], best[j]});
        }
      };
      int cnt = 0;
      ll tot = have + add;
      for (int i = 0; i < size(adj[cent]) && cnt < 2; i++) {
        if (dead[adj[cent][i][0]])
          continue;
        yeet(best[adj[cent][i][0]]);
        tot += depth[best[adj[cent][i][0]]];
        cnt++;
      }
      ans[2] = max(ans[2], tot);
      while (size(pq)) {
        const auto [v, i] = pq.top();
        pq.pop();
        if (seen[i])
          continue;
        cnt++, tot += v;
        ans[cnt] = max(ans[cnt], tot);
        yeet(i);
      }
      for (const auto &i : nodes) {
        seen[i] = 0;
      }
      nodes.clear();
      dead[cent] = 1;
      for (const auto &[j, c, d] : adj[cent])
        if (!dead[j])
          self(self, j, subtree[cent] - subtree[j] - d + c + add);
    };
    decomp(decomp, 0, 0);
  }
  FOR(i, 1, N)
    ans[i] = max(ans[i], ans[i-1]);
  int Q;
  cin >> Q;
  while (Q--) {
    int v; cin >> v;
    cout << sum - ans[v] << '\n';
  }
}

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