Submission #1062774

#TimeUsernameProblemLanguageResultExecution timeMemory
1062774vuavisaoJobs (BOI24_jobs)C++17
40 / 100
91 ms33732 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; using ll = long long; const int N = 300'000 + 10; const ll INF = 1'000'000'000'000'000'000; int n; ll s; vector<int> g[N]; ll cost[N]; int parent[N]; namespace sub1 { bool check() { return (s == INF); } ll dp[N]; void dfs(int u) { dp[u] = cost[u]; for (const auto& v : g[u]) { dfs(v); dp[u] += dp[v]; } dp[u] = max(dp[u], 0ll); } void solve() { dfs(0); // for (int u = 1; u <= n; ++ u) cout << dp[u] << " \n"[u == n]; cout << dp[0]; } } namespace sub23 { bool check() { for (int u = 1; u <= n; ++ u) { if (parent[u] != 0 && parent[u] != u - 1) return false; } return true; } ll sum[N], mi[N]; void solve() { ll first = s; vector<pair<ll, ll>> candidates; mi[0] = INF; for (int u = 1; u <= n; ++ u) { int p = parent[u]; ll add = sum[p] + cost[u]; mi[u] = min(mi[p], add); if (add > 0) { candidates.push_back(make_pair(-mi[u], add)); sum[u] = 0; } else { sum[u] = add; } } sort(candidates.begin(), candidates.end()); for (const auto& [need, add] : candidates) { if (s - need < 0) { break; } s += add; } cout << s - first; } } namespace sub4 { bool check() { return (n <= 2'000); } ll mi[N], sum[N]; void dfsRem(int u, int& best) { int p = parent[u]; ll add = sum[p] + cost[u]; mi[u] = min(mi[p], add); if (add > 0) { if (best == -1 || mi[u] > mi[best]) { best = u; } return; } for (const auto& v : g[u]) { dfsRem(v, best); } } void solve() { ll first = s; for (int cnt = 1; cnt <= 2'000; ++ cnt) { int best = -1; for (int u = 0; u <= n; ++ u) { mi[u] = INF; sum[u] = 0; } dfsRem(0, best); if (best == -1 || -mi[best] > s) { break; } ll ss = 0; while (best != 0) { ss += cost[best]; cost[best] = 0; best = parent[best]; } s += ss; } cout << s - first; } } int32_t main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); cin >> n >> s; for (int u = 1; u <= n; ++ u) { cin >> cost[u] >> parent[u]; g[parent[u]].push_back(u); } if (sub1::check()) { sub1::solve(); return 0; } if (sub23::check()) { sub23::solve(); return 0; } if (sub4::check()) { sub4::solve(); return 0; } assert(false); return (0 ^ 0); } /// Code by vuavisao
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...