| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 113463 | Beautiful_Times | 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>
#include <queue>
#include <vector>
#include <friend.h>
using namespace std;
vector<int> child[100001];
int cod[6];
int ho[6];
int pro[6];
int dpp[100001][2];
int conn[100001];
int dp(int node, bool inc)
{
int temp;
if(inc)
temp = 1;
else
temp = 0;
if(dpp[node][temp] != -1)
return dpp[node][temp];
if(inc == true)
{
int total = conn[node];
for(int x = child[node].size()-1;x>=0;x-=2)
{
int nn = child[node].at(x-1);
int proc = child[node].at(x);
if(proc == 1)
total += max(dp(nn,true),dp(nn,false));
else
total += dp(nn,false);
}
dpp[node][temp] = total;
}
else
{
int current = 0;
int include2 = 0;
int include1 = 0;
for(int x = child[node].size()-1;x>=0;x-=2)
{
int nn = child[node].at(x-1);
int proc = child[node].at(x);
if(proc == 0)
{
int diff = dp(nn,true) - dp(nn,false);
if(diff <= 0)
current += dp(nn,false);
else
{
if(include1 + diff > include2)
{
current += include1 + dp(nn,true);
current -= include2;
include1 = 0;
include2 = 0;
}
else
{
include1 += diff;
current += dp(nn,false);
}
}
}
else
{
int diff = dp(nn,true) - dp(nn,false);
if(diff < 0)
current += dp(nn,false);
else
{
current += dp(nn,true);
include2 += diff;
}
}
}
dpp[node][temp] = current;
}
return dpp[node][temp];
}
int findSample(int n, int confidence[], int host[], int protocol[])
{
for(int x = 1;x<n;x++)
{
child[host[x]].push_back(x);
child[host[x]].push_back(protocol[x]);
}
for(int x = 0;x<100001;x++)
{
dpp[x][0] = -1;
dpp[x][1] = -1;
}
for(int x = 0;x<n;x++)
{
conn[x] = confidence[x];
}
return max(dp(0,false),dp(0,true));
}
int main()
{
cod[0] = 13;
cod[1] = 3;
cod[2] = 6;
cod[3] = 20;
cod[4] = 10;
cod[5] = 15;
ho[1] = 0;
ho[2] = 0;
ho[3] = 1;
ho[4] = 2;
ho[5] = 0;
pro[1] = 0;
pro[2] = 1;
pro[3] = 2;
pro[4] = 1;
pro[5] = 0;
cout << findSample(6,cod,ho,pro) << endl;
for(int x = 0;x<child[0].size();x++)
cout << child[0].at(x) << " ";
cout << endl;
for(int x = 0;x<6;x++)
{
cout << dpp[x][0] << " " << dpp[x][1] << endl;
}
}