제출 #1256753

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

worst_reporter2

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

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

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

  int n;
  std::cin >> n;

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

  std::vector<int> norm;

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

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());
  
  for (int &x : h) {
    x = std::lower_bound(norm.begin(), norm.end(), x) - norm.begin() + 1;
  }

  std::vector<bool> isRoot(n, false);
  std::vector<int> vis(n, 0);
  std::vector<bool> oncyc(n, false);

  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
    int j = i;
    while (!vis[j]) {
      vis[j] = i + 1;
      j = parent[j];
    }
    if (vis[j] == i + 1) {
      std::vector<int> cycle;
      while (vis[j] == i + 1) {
        vis[j] = -1;
        cycle.push_back(j);
        j = parent[j];
      }
      std::sort(cycle.begin(), cycle.end(), [&](int u, int v) {
        return h[u] < h[v];
      });
      if ((int) cycle.size() > 1) {
        for (int u : g[cycle[0]]) {
          if (vis[u] == -1) {
            g[cycle[0]].erase(std::find(g[cycle[0]].begin(), g[cycle[0]].end(), u));
            break;
          }
        }
      }
      for (int j = 1; j < (int) cycle.size(); j++) {
        for (int u : g[cycle[j]]) {
          if (vis[u] != -1) {
            g[cycle[0]].push_back(u);
          }
        }
        g[cycle[j]].clear();
        g[cycle[j]].push_back(cycle[j - 1]);
      }
      isRoot[cycle.back()] = true;
    }
  }
  
  std::vector<std::map<int, ll>> delta(n);
  
  auto dfs = [&](auto &&self, int u) -> void {
    for (int v : g[u]) {
      self(self, v);
    }

    for (int v : g[u]) {
      if (delta[u].size() < delta[v].size()) {
        std::swap(delta[u], delta[v]);
      }
      for (const auto &[h, c] : delta[v]) {
        delta[u][h] += c;
      }
    }

    delta[u][h[u]] += c[u];
    auto it = delta[u].lower_bound(h[u]);
    if (it == delta[u].begin()) {
      return;
    }
    it = std::prev(it);
    ll val = c[u];
    std::vector<int> rem;
    while (val) {
      ll take = std::min(val, it -> second);
      it -> second -= take;
      val -= take;
      if (it -> second == 0) {
        rem.push_back(it -> first);
      }
      if (it == delta[u].begin()) {
        break;
      }
      it = std::prev(it);
    }
    for (int h : rem) {
      delta[u].erase(h);
    }
  };
  
  for (int i = 0; i < n; i++) {
    if (isRoot[i]) {
      dfs(dfs, i);
      // 1. schimb pe toate de pe ciclu
      for (const auto &[h, c] : delta[i]) {
        answer -= c;
      }
      // 2. nu schimb pe i
    }
  }

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

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