| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1064493 | anango | Holiday (IOI14_holiday) | C++17 | 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 "friend.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define mex max
int INF = 1LL<<60;
// Find out best sample
signed findSample(signed n,signed confidence[],signed host[],signed protocol[]){
int ans=10;
//let 0 denote i, 1 denote the friends of i
//let dp0[i] = answer if we are allowed 0 or 1
//dp1[i] = answer if we're only allowed 0
//dp2[i] = answer if we're only allowed 1
//dp3[i] = answer if we're allowed neither
//in the subtree of i
//actually,
//dp0[i] = answer if we didn't use any friends of i so far
//dp1[i] = answer if we did use some friend of i so far
//no it doesn't work
//dp0[i] = answer if we didn't use i
//dp1[i] = answer if we did use i
vector<int> dp0(n,0);
vector<int> dp1;
for (int i=0; i<n; i++) dp1.push_back(confidence[i]);
for (int i=n-1; i>=1; i--) {
int parent = host[i];
int jambloooooooooatautautau = protocol[i];
int x = dp0[parent];
int y = dp1[parent];
int z = dp0[i];
int w = dp1[i];
int newx = -INF;
int newy = -INF;
if (jambloooooooooatautautau==0) {
newx=x+w;
newy=y+z;
}
else if (jambloooooooooatautautau==1) {
newx=x+z;
newy=y+w;
}
else if (jambloooooooooatautautau==2) {
newx=x+z;
newy=max(y+z,x+w);
}
dp0[parent] = newx;
dp1[parent] = newy;
dp1[parent]=max(dp0[parent],dp1[parent]);
//cout << "transition " << jambloooooooooatautautau <<" " << i <<" " << x<< " " << y <<" " <<z <<" " << w <<" " << newx <<" " << newy << endl;
}
for (int i=0; i<n; i++) {
//cout << i <<" " << dp0[i] <<" " << dp1[i] << endl;
}
int mans = max(dp0[0],dp1[0]);
return mans;
}