Submission #1064892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064892		Edu175	Friend (IOI14_friend)	C++17	100 / 100	30 ms	8252 KiB

friend

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fdgkj:v)cout<<fdgkj<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e5+5;
int findSample(int n,int c[],int ps[],int ts[]){
	vector<vector<ll>>dp(n,vector<ll>(2));
	for(ll x=n-1;x>=0;x--){
		ll p=ps[x],t=ts[x];
		// cerr<<"cero "<<dp[0][0]<<" "<<dp[0][1]<<"\n";
		dp[x][1]+=c[x];
		// cerr<<x<<": "<<dp[x][0]<<" "<<dp[x][1]<<"\n";
		if(!x)break;
		if(!t){
			dp[p][0]+=max(dp[x][1],dp[x][0]);
			dp[p][1]+=dp[x][0];
		}
		else {
			if(t==1){
				dp[p][1]=max(max(dp[p][1],dp[p][0]-c[p])+dp[x][1],
							dp[p][1]+dp[x][0]);
			}
			else {
				dp[p][1]=max(dp[p][0]-c[p]+dp[x][1],
							dp[p][1]+dp[x][0]);
			}
			dp[p][0]+=dp[x][0];
		}
	}
	ll res=max(dp[0][0],dp[0][1]);
	return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31