This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "friend.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n;
int c[MAXN];
int dp[MAXN][2];
bool bl[MAXN][2];
std::vector <int> g[MAXN];
int f(int node, bool can)
{
if (bl[node][can])
{
return dp[node][can];
}
bl[node][can] = true;
int sumTake = c[node];
int sumNotTake = 0;
for (const int &u : g[node])
{
sumTake += f(u, 0);
sumNotTake += f(u, 1);
}
dp[node][can] = sumNotTake;
if (can) dp[node][can] = std::max(dp[node][can], sumTake);
return dp[node][can];
}
int findSample(int N, int confidence[], int host[], int protocol[])
{
n = N;
for (int i = 0 ; i < n ; ++i)
{
c[i] = confidence[i];
}
for (int i = 1 ; i < n ; ++i)
{
g[host[i]].push_back(i);
}
return f(0, 1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |