Submission #994669

#TimeUsernameProblemLanguageResultExecution timeMemory
994669pavementJobs (BOI24_jobs)C++17
14 / 100
2060 ms26452 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define int long long using ll = long long; int N, x[300005], p[300005]; ll ans, s, os, wei[300005], mn[300005]; bool seen[300005]; vector<int> adj[300005]; void dfs(int u) { wei[u] += x[u]; mn[u] = min(mn[u], wei[u]); for (auto v : adj[u]) { wei[v] = wei[u]; mn[v] = mn[u]; dfs(v); } } main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> s; os = s; for (int i = 1; i <= N; i++) { cin >> x[i] >> p[i]; adj[p[i]].pb(i); } seen[0] = 1; ans = s; while (1) { for (int i = 1; i <= N; i++) { mn[i] = 0; } dfs(0); pair<ll, int> tk = mp(LLONG_MIN, -1); for (int i = 1; i <= N; i++) { if (seen[i]) { assert(mn[i] == 0 && wei[i] == 0); } if (!seen[i] && s + mn[i] >= 0) { //~ cout << "OPTION " << i << '\n'; tk = max(tk, mp(wei[i], i)); } } if (tk.second == -1) { break; } s += tk.first; ans = max(ans, s); for (int j = tk.second; !seen[j]; j = p[j]) { seen[j] = 1; x[j] = 0; } } cout << ans - os << '\n'; }

Compilation message (stderr)

Main.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~
#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...