Submission #1009287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009287		hotboy2703	Friend (IOI14_friend)	C++14	100 / 100	17 ms	4188 KiB

friend

#include "friend.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

// Find out best sample
ll dp[100100][2];
int findSample(int n,int confidence[],int p[],int protocol[]){
	for (ll i = 0;i < n;i ++){
        dp[i][1] = confidence[i];
        dp[i][0] = 0;
	}
	for (ll i = n - 1;i >= 1;i --){
        ll type = protocol[i];
        ll pre[2];
        pre[0] = dp[p[i]][0];
        pre[1] = dp[p[i]][1];
        dp[p[i]][0] = pre[0] + dp[i][0];
        dp[p[i]][1] = pre[1] + dp[i][0];
        if (type==0){
            dp[p[i]][0] = max(dp[p[i]][0],pre[0] + dp[i][1]);
        }
        else if (type==1){
            dp[p[i]][1] = max({dp[p[i]][1],pre[0] + dp[i][1],pre[1] + dp[i][1]});
        }
        else{
            dp[p[i]][1] = max(dp[p[i]][1],pre[0] + dp[i][1]);
        }
	}
	return max(dp[0][0],dp[0][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