제출 #1189934

#제출 시각아이디문제언어결과실행 시간메모리
1189934anmattroiJobs (BOI24_jobs)C++17
11 / 100
71 ms31812 KiB
#include <bits/stdc++.h> #define maxn 300005 using namespace std; int n; int64_t s; int c[maxn], p[maxn], start[maxn], stop[maxn], id = -1, euler[maxn]; int64_t sum[maxn], dp[maxn]; vector<int> adj[maxn]; void dfs(int u) { start[u] = ++id; euler[id] = u; sum[u] += c[u]; for (int v : adj[u]) { dfs(v); sum[u] += sum[v]; } stop[u] = id; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> s; for (int i = 1; i <= n; i++) cin >> c[i] >> p[i]; for (int i = 1; i <= n; i++) adj[p[i]].emplace_back(i); dfs(0); int64_t ans = 0; for (int i = 1; i <= n; i++) ans += c[i]; for (int i = n; i >= 0; i--) dp[i] = max(dp[stop[euler[i]]+1] - sum[euler[i]], dp[i+1]); cout << ans + dp[0]; } /* 6 1 3 0 -3 1 -5 0 2 1 6 3 -4 5 6 */
#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...