제출 #1256575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256575		LucaLucaM	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	2094 ms	111764 KiB

worst_reporter2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::vector<int> h(n), c(n);
  std::vector<std::vector<int>> g(n);

  ll answer = 0;
  for (int i = 0; i < n; i++) {
    int p;
    std::cin >> p >> h[i] >> c[i];
    p--;
    answer += c[i];
    if (p != i) {
      g[p].push_back(i);
    }
  }

  std::vector<std::map<int, ll>> dp(n);

  auto keepBest = [&](int u) {
    std::vector<std::pair<int, ll>> st;
    std::vector<int> rem;
    for (const auto &[h, c] : dp[u]) {
      while (!st.empty() && st.back().second <= c) {
        rem.push_back(st.back().first);
        st.pop_back();
      }
      st.push_back({h, c});
    }
    for (int h : rem) {
      dp[u].erase(h);
    }
  };

  auto merge = [&](int u, int v) {
    for (const auto &[h, c] : dp[u]) {
      dp[u][h] += (dp[v].lower_bound(h)) -> second;
    }
  };

  auto dfs = [&](auto &&self, int u) -> void {
    int heavySon = -1;
    for (int v : g[u]) {
      self(self, v);
      if (heavySon == -1 || dp[v].size() > dp[heavySon].size()) {
        heavySon = v;
      }
    }
    if (heavySon == -1) {
      dp[u][1] = dp[u][+1e9] = 0;
      dp[u][h[u]] = c[u];
      keepBest(u);
      return;
    }

    std::swap(dp[u], dp[heavySon]);
    std::vector<int> calc;
    calc.push_back(h[u]);

    g[u].erase(std::find(g[u].begin(), g[u].end(), heavySon));

    for (int v : g[u]) {
      for (const auto &[h, c] : dp[v]) {
        if (!dp[u].count(h)) {
          calc.push_back(h);
        }
      }
    }
      
    std::sort(calc.begin(), calc.end());
    calc.erase(std::unique(calc.begin(), calc.end()), calc.end());
    std::vector<ll> nw;

    for (int h : calc) {
      nw.push_back(dp[u].lower_bound(h) -> second);
    }

    for (int i = 0; i < (int) nw.size(); i++) {
      dp[u][calc[i]] = nw[i];
    }
    
    for (int v : g[u]) {
      merge(u, v);
    }
    dp[u][h[u]] += c[u]; 
    keepBest(u);
  };

  dfs(dfs, 0);

  ll maxi = 0;

  for (const auto &[x, y] : dp[0]) {
    maxi = std::max(maxi, y); 
  }
  
  answer -= maxi;

  std::cout << answer;
  
  return 0;
}

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