# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
155148 | 2019-09-26T17:05:31 Z | Mercenary | Friend (IOI14_friend) | C++14 | 0 ms | 0 KB |
#include "friend.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int dp[maxn][2]; vector<int> v[maxn]; int findSample(int n,int confidence[],int host[],int protocol[]){ for(int i = 1 ; i < n ; ++i){ v[host[i]].pb(i); } for(int i = n - 1 ; i >= 0 ; --i){ dp[i][0] = confidence[i]; for(int c : v[i]){ if(protocol[c] == 0){ dp[i][0] += dp[c][1]; dp[i][1] += dp[i][0]; }else if(protocol[c] == 1){ dp[i][0] += dp[c][0]; dp[i][1] += dp[c][1]; }else{ dp[i][0] = dp[c][1]; dp[i][1] = dp[c][1]; } } } return max(dp[0][0],dp[0][1]); }