제출 #1232596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232596		asdfgrace	Jobs (BOI24_jobs)	C++20	11 / 100	82 ms	32836 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define parr(x) dbg(cerr << #x << " = "; for (auto y : x) {cerr << y << ' ';} cerr << '\n';)
#define parr2d(x) dbg(cerr << #x << " = \n"; for (auto _ : x) {parr(_);} cerr << '\n';)

/*
if there are cycles, just don't consider them
they will stand out and not be connected to node 0

note that this is like a tree
you start from node 0 & can have multiple traversors, but you must go down the tree step by step
answer to subtask 1 is just the maximum smth idk
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; long long s;
  cin >> n >> s;
  vector<long long> a(n + 1), par(n + 1);
  vector<vector<int>> edges(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> par[i];
    edges[par[i]].push_back(i);
  }
  vector<long long> dp(n + 1, 0);
  function<void(int)> dfs = [&] (int node) {
    dp[node] = a[node];
    for (auto next : edges[node]) {
      dfs(next);
      dp[node] += dp[next];
    }
    dp[node] = max(dp[node], 0ll);
  };
  dfs(0);
  cout << dp[0] << '\n';
}

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