제출 #994614

#제출 시각아이디문제언어결과실행 시간메모리
994614pavementJobs (BOI24_jobs)C++17
14 / 100
2063 ms24048 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back using ll = long long; int N, x[300005], p[300005]; ll 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] = min(mn[v], mn[u]); dfs(v); } } int 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; while (1) { for (int i = 1; i <= N; i++) { mn[i] = 0; } dfs(0); pair<ll, int> tk = mp(-1, -1); for (int i = 1; i <= N; i++) { if (!seen[i] && s + mn[i] >= 0) { tk = max(tk, mp(wei[i], i)); } } if (tk.first < 0) { break; } s += tk.first; for (int j = tk.second; !seen[j]; j = p[j]) { seen[j] = 1; x[j] = 0; } } cout << s - os << '\n'; }
#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...