Submission #1040074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040074		abczz	Friend (IOI14_friend)	C++17	100 / 100	15 ms	8172 KiB

friend

#include "friend.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long
 
using namespace std;
 
vector <ll> adj[100000];
ll dp[100000][4], cur[8][2], p, c, f = 0;
int findSample(int n,int confidence[],int host[],int protocol[]) {
	for (int i=0; i<n; ++i) {
		dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = 0;
	}
	for (int i=n-1; i>0; --i) {
		p = host[i], c = confidence[i];
		if (protocol[i] == 0) {
			dp[p][2] += max(dp[i][0], dp[i][1]);
			dp[p][3] = max(dp[p][3] + max(dp[i][0], dp[i][1]), max(dp[p][0], dp[p][1]) + max(max(dp[i][0], dp[i][2]) + c, max(dp[i][1], dp[i][3])));
			dp[p][0] += max(dp[i][0], dp[i][1]);
      dp[p][1] += max(max(dp[i][0] + c, dp[i][1]), max(dp[i][2]+c, dp[i][3]));
		}
		else if (protocol[i] == 1) {
			dp[p][2] += max(max(dp[i][0] + c, dp[i][1]), max(dp[i][2] + c, dp[i][3]));
			dp[p][3] += max(max(dp[i][0] + c, dp[i][1]), max(dp[i][2] + c, dp[i][3]));
			dp[p][0] += max(dp[i][0], dp[i][1]);
      dp[p][1] += max(dp[i][0], dp[i][1]);
		}
    else {
			dp[p][2] += max(dp[i][0], dp[i][1]);
			dp[p][3] = max(dp[p][3] + max(dp[i][0], dp[i][1]), max(dp[p][0], dp[p][1]) + max(max(dp[i][0], dp[i][2]) + c, max(dp[i][1], dp[i][3])));
      dp[p][0] += max(dp[i][0], dp[i][1]);
			dp[p][1] += max(dp[i][0], dp[i][1]);
    }
	}
	dp[0][0] += confidence[0], dp[0][2] += confidence[0];
	for (int i=0; i<4; ++i) {
		f = max(f, dp[0][i]);
	}
	return f;
}

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