| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 873409 | HuyQuang_re_Zero | 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 <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
//#include "friend.h"
using namespace std;
int n,i,f0[100005],f1[100005],c[100005],host[100005],type[100005],u;
int findSample(int n,int c[],int host[],int type[])
{
for(u=0;u<n;u++) f0[u]=0,f1[u]=c[u];
for(i=n-1;i>=1;i--)
{
int v=i,u=host[i],k=type[i];
if(k==0)
{
f1[u]+=f0[v];
f0[u]=f0[u]+max(f0[v],f1[v]);
}
else if(k==1)
{
f1[u]=max(max(f1[u]+f0[v],f0[u]+f1[v]),f1[u]+f1[v]);
f0[u]+=f0[v];
}
else
{
f1[u]=max(f1[u]+f0[v],f0[u]+f1[v]);
f0[u]+=f0[v];
}
}
return max(f0[0],f1[0]);
}
/*
int main()
{
freopen("friend.inp","r",stdin);
freopen("friend.out","w",stdout);
cin>>n;
for(i=0;i<n;i++) cin>>c[i];
for(i=1;i<n;i++) cin>>host[i]>>type[i];
cout<<findSample(n,c,host,type);
}
*/