Submission #397120

#	Time	Username	Problem	Language	Result	Execution time	Memory
397120		fedoseevtimofey	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	426 ms	112936 KiB

worst_reporter2

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
 
ll smart(vector <int> a, vector <int> h, vector <int> c) {
  int n = a.size();
  vector <vector <int>> g(n);
  for (int i = 0; i < n; ++i) {
    --a[i];
    if (a[i] != i) {
      g[a[i]].push_back(i);
    }
  }
  vector <map <int, ll>> dp(n);
  auto dfs = [&] (int u, int p, auto&& dfs) -> void {
    for (auto v : g[u]) {
      if (v != p) {
        dfs(v, u, dfs);
        if (dp[v].size() > dp[u].size()) swap(dp[u], dp[v]);
        for (auto p : dp[v]) dp[u][p.first] += p.second;
      }
    }
    dp[u][1] += c[u];
    dp[u][h[u]] -= c[u];
    dp[u][h[u] + 1] += c[u];

    /*cout << "start " << u + 1 << endl;
    for (auto p : dp[u]) {
      cout << p.first << ' ' << p.second << endl;
    }
    cout << "finish" << endl;*/
    auto it = dp[u].find(h[u]);
    while (it->second < 0) {
      auto jt = prev(it);
      jt->second += it->second;
      dp[u].erase(it);
      it = jt;
    }
    /*cout << "start " << u + 1 << endl;
    for (auto p : dp[u]) {
      cout << p.first << ' ' << p.second << endl;
    }
    cout << "finish" << endl;*/
  };
  dfs(0, -1, dfs);
  if (dp[0].empty() || dp[0].begin()->first > 1) {
    return 0LL;
  } else {
    return dp[0].begin()->second;
  }
}

ll stupid(vector <int> a, vector <int> h, vector <int> c) {
  int n = a.size();
  vector <vector <int>> g(n);
  for (int i = 0; i < n; ++i) {
    --a[i];
    if (a[i] != i) {
      g[a[i]].push_back(i);
    }
  }
vector <map <int, ll>> dp(n);
  auto dfs = [&] (int u, int p, auto&& dfs) -> void {
    for (auto v : g[u]) {
      if (v != p) {
        dfs(v, u, dfs);
        if (dp[v].size() > dp[u].size()) swap(dp[u], dp[v]);
        for (auto p : dp[v]) dp[u][p.first] += p.second;
      }
    }
    dp[u][1] += c[u];
    dp[u][h[u]] -= c[u];
    dp[u][h[u] + 1] += c[u];
    vector <pair <int, ll>> cur = vector <pair <int, ll>> (dp[u].begin(), dp[u].end());
    for (int i = 1; i < (int)cur.size(); ++i) cur[i].second += cur[i - 1].second;
    for (int i = (int)cur.size() - 2; i >= 0; --i) cur[i].second = min(cur[i].second, cur[i + 1].second);
    dp[u].clear();
    for (int i = 0; i < (int)cur.size(); ++i) {
      if (i == 0 || cur[i].second != cur[i - 1].second) dp[u][cur[i].first] += cur[i].second - (i == 0 ? 0 : cur[i - 1].second); 
    }
  };
  dfs(0, -1, dfs);
  ll ans = 2e18;
  ll sum = 0;
  for (auto p : dp[0]) {
    sum += p.second;
    ans = min(ans, sum);
  }
  return ans;
}

void stress() {
  mt19937 rnd(123);
  int tt = 1000;
  while (tt--) {
    int n = rnd() % 5 + 1;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) {
      a[i] = rnd() % (i + 1) + 1;
    }
    vector <int> h(n), c(n);
    for (int i = 0; i < n; ++i) {
      h[i] = rnd() % 5 + 1, c[i] = rnd() % 5 + 1;
    }
    if (smart(a, h, c) != stupid(a, h, c)) {
      cout << n << '\n';
      for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ' << h[i] << ' ' << c[i] << endl;
      }
      exit(0);
    }
    if (tt % 10 == 0) {
      cout << tt << endl;
    }
  }
  exit(0);
}

void run() {
  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];
  }
  cout << smart(a, h, c) << endl;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  //stress();
  run();
}

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