제출 #995326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995326		MilosMilutinovic	Jobs (BOI24_jobs)	C++14	100 / 100	373 ms	116304 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  long long s;
  cin >> s;
  n += 1;
  vector<int> x(n);
  vector<int> p(n);
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    cin >> x[i] >> p[i];
    g[p[i]].push_back(i);
  }
  x[0] = 0;
  p[0] = -1;
  vector<multiset<pair<long long, long long>>> profit(n);
  vector<long long> inc(n);
  vector<int> where(n);
  function<void(int)> Dfs = [&](int v) {
    for (int u : g[v]) {
      Dfs(u);
    }
    if (x[v] >= 0) {
      where[v] = v;
      profit[where[v]].emplace(0, x[v]);
      for (int u : g[v]) {
        if (profit[where[u]].size() > profit[where[v]].size()) {
          swap(where[u], where[v]);
        }
        for (auto p : profit[where[u]]) {
          profit[where[v]].insert(p);
        }
      }
    } else {
      where[v] = v;
      for (int u : g[v]) {
        if (profit[where[u]].size() > profit[where[v]].size()) {
          swap(where[u], where[v]);
        }
        for (auto p : profit[where[u]]) {
          profit[where[v]].insert(p);
        }
      }
      long long dec = abs(x[v]);
      long long mx = abs(x[v]);
      long long bal = abs(x[v]);
      while (dec > 0 && !profit[where[v]].empty()) {
        mx = max(mx, bal + profit[where[v]].begin()->first);
        long long t = min(dec, profit[where[v]].begin()->second);
        dec -= t;
        bal -= t;
        pair<long long, long long> tmp = *profit[where[v]].begin();
        profit[where[v]].erase(profit[where[v]].begin());
        tmp.second -= t;
        if (tmp.second > 0) {
          profit[where[v]].insert(tmp);
        }
      }
      long long sum = 0;
      while (!profit[where[v]].empty() && profit[where[v]].begin()->first <= mx) {
        sum += profit[where[v]].begin()->second;
        profit[where[v]].erase(profit[where[v]].begin());
      }
      if (sum > 0) {
        profit[where[v]].emplace(mx, sum);
      }
    }
  };
  Dfs(0);
  long long start = s;
  long long res = 0;
  for (auto p : profit[where[0]]) {
    if (s >= p.first) {
      s += p.second;
    }
  }
  cout << s - start << '\n';
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:77:13: warning: unused variable 'res' [-Wunused-variable]
   77 |   long long res = 0;
      |             ^~~

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