Submission #1184364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184364		TroySer	Friend (IOI14_friend)	C++20	50 / 100	1 ms	328 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;
using ll = int;

struct Answer {
	ll take;
	ll dontTake;
};

// Find out best sample
int findSample(int N, int confidence[], int host[], int protocol[]) {
	
	vector<Answer> memo(N, Answer{0, 0});

	for (ll i = 0; i < N; i++) {
		memo[i].take = confidence[i];
		memo[i].dontTake = 0;
	}

	// root is 0
	// host ---(protocol)---> other dude
	for (ll i = N - 1; i >= 1; i--) {
		ll currentNode = host[i], v = i;
		if (protocol[i] == 0) { // if its "I'm your friend"
			memo[currentNode].take += memo[v].dontTake; // if you take current, you are not allowed to take next
			memo[currentNode].dontTake += max(memo[v].take, memo[v].dontTake); // you're allowed to do either
		} else if (protocol[i] == 1) {
			memo[currentNode].take = max(
				{
					memo[currentNode].take + memo[v].take,
					memo[currentNode].take + memo[v].dontTake,
					memo[currentNode].dontTake + memo[v].take, 
				}
			);
			memo[currentNode].dontTake += memo[v].dontTake; // you're allowed to do either
		} else if (protocol[i] == 2) {
			memo[currentNode].take += max(memo[currentNode].take + memo[v].dontTake, memo[currentNode].dontTake + memo[v].take);
			memo[currentNode].dontTake += memo[v].dontTake; // you're allowed to do either
		}
	}

	return max(memo[0].take, memo[0].dontTake);

}

// const ll MAX_N = 1e5;
// int confidence[MAX_N];
// int host[MAX_N];
// int protocol[MAX_N];

// int main() {

// 	ll N;
// 	cin >> N;
	
// 	for (ll i = 0; i < N; i++) cin >> confidence[i];

// 	for (ll i = 1; i < N; i++) {
// 		cin >> host[i] >> protocol[i];
// 	}

// 	ll res = findSample(N, confidence, host, protocol);
// 	cout << "Output: " << res << endl;

// }

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