제출 #1052882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052882		vjudge1	Jobs (BOI24_jobs)	C++17	40 / 100	192 ms	28868 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18;
const int N = 3e5+10;
int n, p[N];
ll s, x[N];
vector<int> child[N];


ll dfs(int v)
{
  for(int c : child[v])
    x[v] += dfs(c);
  return max(x[v], 0ll);
}

void subtask1()
{
  cout << dfs(0) << endl;
  exit(0);
}

int main()
{
  cin >> n >> s;
  for(int i = 1; i <= n; i ++)
    {
      cin >> x[i] >> p[i];
      child[p[i]].push_back(i);
    }

  if(s == inf) subtask1();

  set<pair<ll, int> > st;
  for(int i = 1; i <= n; i ++)
    if(p[i] == 0) st.insert({x[i], i});

  ll init = s;
  while(st.size())
    {
      int v = st.rbegin()->second;
      st.erase(--st.end());
      if(s + x[v] >= 0)
	{
	  if(child[v].empty())
	    s += max(0ll, x[v]);
	  else
	    {
	      int c = child[v][0];
	      if(x[v] >= 0) s += x[v];
	      else x[c] += x[v];
	      st.insert({x[c], c});
	    }
	}
    }
  cout << s - init << endl;
  return 0; 
}

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