Submission #1107121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107121		LucaLucaM	Jobs (BOI24_jobs)	C++17	0 / 100	2052 ms	27724 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];

ll dfs(int u, ll money) {
  if (money < 0) {
    return 0;
  }
  if (g[u].empty()) { 
    if (a[u] > 0) {
      ll aux = a[u];
      a[u] = 0;
      return aux;
    }
    return 0;
  }
  ll ret = 0;
  if (a[u] > 0) {
    money += a[u];
    ret += a[u];
    a[u] = 0;
  }
  for (int rep = 0; rep <= 2001; rep++) { 
    ll aici = 0;
    for (const auto &v : g[u]) {  
      ll aux = dfs(v, money + a[u]);
      if (aux > 0) {
        ret += a[u];
        aici += a[u];
        money += a[u];
        a[u] = 0;
        ret += aux;
        aici += aux;
        money += aux;
      }
    }
    if (aici == 0) {
      break;
    }
  }
  return ret;
}

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 start = a[0];
  std::cout << dfs(0, 0) - start;

  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: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31