제출 #775635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775635		alvingogo	Friend (IOI14_friend)	C++14	100 / 100	28 ms	3404 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
// Find out best sample

int findSample(int n,int w[],int fa[],int p[]){
	vector<int> dp(n),dp2(n);
	for(int i=n-1;i>=0;i--){
		dp[i]=w[i];
	}
	for(int i=n-1;i>0;i--){
		int a=dp[fa[i]],b=dp2[fa[i]];
		if(p[i]==0){
			dp[fa[i]]+=dp2[i];
			dp2[fa[i]]+=max(dp2[i],dp[i]);
		}
		else if(p[i]==1){
			dp[fa[i]]=max({a+dp[i],b+dp[i],a+dp2[i]});
			dp2[fa[i]]+=dp2[i];
		}
		else{
			dp[fa[i]]=max(a+dp2[i],b+dp[i]);
			dp2[fa[i]]+=dp2[i];
		}
	}
	return max(dp[0],dp2[0]);
}

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