Submission #1097501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097501		duckindog	Jobs (BOI24_jobs)	C++17	40 / 100	109 ms	65616 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 300'000 + 10;
int n, fund, total;
int profit[N];
vector<pair<int, int>> ad[N];
int par[N];

namespace sub1 { 
  int f[N];
  void dfs(int u) { 
    auto& ret = f[u];
    for (const auto& [v, w] : ad[u]) { 
      dfs(v);
      if (f[v] + w > 0) ret += f[v] + w;
    }
  }
  
  void solve() { 
    dfs(0);
    cout << f[0] << "\n";
  }
}

namespace sub3 { 
  int d[N], mi[N];
  
  vector<int> nxt[N];
  void dfs(int u, int pre) {
    if (d[u] > 0) { 
      if (u) nxt[pre].push_back(u);
      pre = u;
    }

    for (const auto& [v, w] : ad[u]) { 
      if (pre == u) { 
        d[v] = 0 + w;
        mi[v] = min(0ll, w);
      } else { 
        d[v] = d[u] + w;
        mi[v] = min(d[v], mi[u]);
      }
      dfs(v, pre);
    }
  }

  void solve() { 
    dfs(0, 0);

    using pii = pair<int, int>;
    priority_queue<pii> q;

    for (const auto& x : nxt[0]) q.push({mi[x], x});
    while (q.size()) { 
      auto [minimum, u] = q.top(); q.pop();
      
      if (total < -minimum) break;
      total += d[u];
      for (const auto& v : nxt[u]) q.push({mi[v], v});
    }
    
    cout << total - fund << "\n";
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> fund;
  for (int i = 1; i <= n; ++i) { 
    int w, p; cin >> w >> p;
    par[i] = p;
    // cerr << p << " " << i << " " << w << "\n";
    ad[p].push_back({i, profit[i] = w});
  }
  total = fund;

  if (fund == 1e18) { sub1::solve(); return 0; }
  
  bool sub3 = true;
  for (int i = 1; i <= n; ++i) sub3 &= (!par[i] || par[i] == i - 1);
  if (sub3) { sub3::solve(); return 0; }
}

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