| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 424208 | Charis02 | Friend (IOI14_friend) | C++14 | 0 ms | 0 KiB |
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 "grader.h"
#include<iostream>
#include<vector>
#include<string.h>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1004
using namespace std;
vector < int > graph[N];
int conf[N];
int dp[N][2];
int calc(int cur,int par,bool choose)
{
int res = 0;
if(dp[cur][choose]!=-1)
return dp[cur][choose];
if(choose)
{
res = conf[cur];
rep(i,0,graph[cur].size())
{
int v = graph[cur][i];
if(v == par)
continue;
res += calc(cur,v,0);
}
}
else
{
rep(i,0,graph[cur].size())
{
int v = graph[cur][i];
if(v == par)
continue;
res += max(calc(cur,v,0),calc(cur,v,1));
}
}
return res;
}
int findSample(int n,int confidence[],int host[],int protocol[])
{
rep(i,0,n)
{
conf[i] = confidence[i];
if(i == 0)
continue;
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
memset(dp,-1,sizeof dp);
return max(calc(1,1,0),calc(1,1,1));
}