Submission #389274

#	Time	Username	Problem	Language	Result	Execution time	Memory
389274		rama_pang	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	693 ms	127660 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;

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

  int N;
  cin >> N;

  vector<int> A(N), H(N), C(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> H[i] >> C[i];
    A[i]--;
  }

  { // Coordinate Compression
    vector<int> coords;
    for (int i = 0; i < N; i++) {
      coords.emplace_back(H[i]);
    }
    sort(begin(coords), end(coords));
    coords.resize(unique(begin(coords), end(coords)) - begin(coords));
    for (int i = 0; i < N; i++) {
      H[i] = lower_bound(begin(coords), end(coords), H[i]) - begin(coords);
    }
  }

  const auto Solve = [&](vector<int> component) -> long long {
    // Cycle + Tree graph
    // Cycle = super root, has many possible costs, try all of them
    //
    // Solve for tree:
    // dp[u][x] = minimum cost when H[u] >= x
    // diff[u][x] = dp[u][x] - dp[u][x - 1]
    //
    // Note:
    // dp[u][x] <= dp[u][x + 1], since dp[u][x] = min(dp[u][x], dp[u][x + 1])
    // 0 <= diff[x + 1]
    //
    // Case 1: Don't change H[u]
    // dp[u][x] = sum(dp[v][H[u]]), for x <= H[u]
    //
    // Case 2: Change H[u]
    // dp[u][x] = C[u] + sum(dp[v][x])

    static vector<int> vis(N);
    static vector<int> outdeg(N);

    for (auto u : component) outdeg[A[u]] += 1;

    vector<int> tree;
    for (auto u : component) if (outdeg[u] == 0) {
      vis[u] = 1;
      tree.emplace_back(u);
    }
    for (int i = 0; i < int(tree.size()); i++) {
      int u = tree[i];
      outdeg[A[u]]--;
      if (outdeg[A[u]] == 0) {
        vis[A[u]] = 1;
        tree.emplace_back(A[u]);
      }
    }

    vector<int> cycle;
    long long sum_cost_cycle = 0;
    map<int, int> value_sum_cost;
    for (auto u : component) {
      if (!vis[u]) {
        cycle.emplace_back(u);
        sum_cost_cycle += C[u];
        value_sum_cost[H[u]] += C[u];
      }
    }

    // For x > H[u]: dp[u][x] = C[u] + sum(dp[v][x])
    //   diff[H[u] + 1] += C[u]
    //
    // For x <= H[u]: dp[u][x] = min(C[u] + sum(dp[v][x]), sum(dp[v][H[u]]))
    //   Let x be greatest, s.t. sum(dp[v][x]) + C[u] < sum(dp[v][H[u]]):
    //   Then C[u] < sum_{x < y <= H[u]}(diff[y])
    //   But for all x + 1 <= y <= H[u]; diff[y] changes to 0.
    //   We can iterate for all y, backwards
    //
    //   diff[x + 1] = sum(dp[v][H[u]]) - sum(dp[v][x]) - C[u]
    //   diff[x + 1] = sum_{x < y <= H[u]}(diff[y]) - C[u]
    //   diff[0] += C[u]

    static vector<map<int, long long>> diff(N + 1);
    diff[N].clear();
    for (auto u : tree) {
      if (!vis[A[u]]) A[u] = N;

      diff[u][H[u] + 1] += C[u];

      long long diffsum = 0;
      while (diff[u].find(H[u] + 1) != begin(diff[u])) {
        auto d = *prev(diff[u].find(H[u] + 1));
        diff[u].erase(diff[u].find(d.first));
        diffsum += d.second;

        if (C[u] < diffsum) {
          diff[u][d.first] += diffsum - C[u];
          diff[u][0] += C[u];
          diffsum = -1;
          break;
        }
      }
      if (diffsum != -1) {
        diff[u][0] += diffsum;
      }

      // Propagate to parent
      if (diff[A[u]].size() < diff[u].size()) {
        swap(diff[A[u]], diff[u]);
      }
      for (auto d : diff[u]) {
        diff[A[u]][d.first] += d.second;
      }
    }

    map<int, long long> dp; dp[0] = 0;
    long long sum = 0;
    for (auto d : diff[N]) {
      sum += d.second;
      dp[d.first] = sum;
    }
    const auto Get = [&](int x) {
      return prev(dp.lower_bound({x + 1}))->second;
    };

    long long ans = Get(0) + sum_cost_cycle;
    for (auto u : cycle) {
      ans = min(ans, sum_cost_cycle - value_sum_cost[H[u]] + Get(H[u]));
    }

    return ans;
  };

  long long ans = 0;

  // Solve for each connected component
  vector<vector<int>> adj(N);
  for (int i = 0; i < N; i++) {
    adj[A[i]].emplace_back(i);
    adj[i].emplace_back(A[i]);
  }
  vector<int> done(N);
  for (int i = 0; i < N; i++) if (!done[i]) {
    done[i] = 1;
    vector<int> que = {i};
    for (int q = 0; q < int(que.size()); q++) {
      int u = que[q];
      for (auto v : adj[u]) if (!done[v]) {
        done[v] = 1;
        que.emplace_back(v);
      }
    }
    ans += Solve(que);
  }

  cout << ans << '\n';
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21