Submission #1107101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107101		LucaLucaM	Jobs (BOI24_jobs)	C++17	14 / 100	2050 ms	25160 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's not the baby, that's my baby

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

const int INF = 1e9;
const int NMAX = 3e5;

ll a[NMAX + 1];
bool vis[NMAX + 1];
ll delta[NMAX + 1];
ll minDelta[NMAX + 1];
std::vector<int> g[NMAX + 1];
int p[NMAX + 1];

void dfs(int u) {
  if (vis[u]) {
    delta[u] = minDelta[u] = 0;
  } else {
    delta[u] += a[u];
    minDelta[u] = std::min(minDelta[u], delta[u]);
  }
  for (const auto &v : g[u]) {
    minDelta[v] = minDelta[u];
    delta[v] = delta[u];
    dfs(v);
  }
}

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

  int n;
  std::cin >> n >> a[0];

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i] >> p[i];
    g[p[i]].push_back(i);
  }
 
  ll money = a[0];
  vis[0] = true;

  for (int rep = 0; rep <= n + 1000; rep++) {
    dfs(0);
    for (int i = 1; i <= n; i++) {
      if (!vis[i] && delta[i] >= 0 && -minDelta[i] <= money) {
        // std::cout << "MONEY: " <<  money << '\n';
        money += delta[i];
        // std::cout << "CHOSE: " << i << '\n';
        int j = i;
        while (!vis[j]) {
          vis[j] = true;
          j = p[j];
        }
        break;
      }
    }
  }

  std::cout << money - a[0] << '\n';

  return 0;
}

Compilation message (stderr)

Main.cpp:5:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    5 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31