Submission #1138459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138459		urosk	친구 (IOI14_friend)	C++20	100 / 100	31 ms	4744 KiB

friend

#include "friend.h"
#include "bits/stdc++.h"
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

using ll = long long;
// Find out best sample
const ll maxn = 100005;
ll dp[2][maxn];
ll n;
ll a[maxn];
ll p[maxn];
int findSample(int N,int confidence[],int host[],int protocol[]){
	n = N;
	for(ll i = 1;i<=n;i++) a[i] = confidence[i-1],p[i] = host[i-1]+1;

	for(ll i = 1;i<=n;i++) dp[1][i] = a[i];
	for(ll i = n;i>=2;i--) {
		ll x = p[i];
		if(protocol[i-1]==0) {
			dp[0][x]+=dp[1][i];
			dp[1][x]+=dp[0][i];
		}else if(protocol[i-1]==1) {
			dp[0][x]+=dp[0][i];
			dp[1][x]+=dp[1][i];
		}else {
			dp[1][x] = max(dp[1][x]+dp[0][i],dp[0][x]+dp[1][i]);
			dp[0][x] += dp[0][i];
		}
		dp[1][x] = max(dp[1][x],dp[0][x]);
	}
	return max(dp[0][1],dp[1][1]);
}

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