Submission #994568

#TimeUsernameProblemLanguageResultExecution timeMemory
994568kymJobs (BOI24_jobs)C++14
0 / 100
2074 ms27220 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #ifdef LOCAL void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) #endif const int MAXN = 300005; const int inf=1000000500ll; const long long oo =1000000000000000500ll; const int MOD = (int)1e9+7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int,int> pi; int n,s; int dp[MAXN]; int A[MAXN], P[MAXN]; vector<int>child[MAXN]; int st[MAXN]; int rev[MAXN]; int TIME; void dfs(int x, int p){ st[x]=TIME; rev[TIME]=x; ++TIME; for(auto v:child[x])if(v!=p){ dfs(v,x); } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> dp[0]; for(int i=1;i<=n;i++)dp[i]=-oo; int ans=0; for(int i=1;i<=n;i++){ cin>>A[i]>>P[i]; child[P[i]].push_back(i); } dfs(0,-1); for(int i=1;i<=n;i++){ int node=rev[i]; for(int j=st[P[node]];j<i;j++){ dp[i]=max(dp[i],dp[j]+A[node]); } ans=max(ans,dp[i]-dp[0]); } cout<<ans; }
#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...