Submission #1184582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184582		TroySer	친구 (IOI14_friend)	C++20	100 / 100	16 ms	2176 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) { // if its all my friends (not me) is friend
			memo[currentNode].take = max(
				{
					memo[currentNode].take + memo[v].dontTake, // i get me, i dont get you
					memo[currentNode].dontTake + memo[v].take,  // i dont get me, i can get you
					memo[currentNode].take + memo[v].take, // i get me, i get you as well
				}
			);
			memo[currentNode].dontTake += memo[v].dontTake; // if i dont take myself and i dont take u, then that means theres some other way
		} else if (protocol[i] == 2) { // all my friends and me are your friend
			memo[currentNode].take = max(
				memo[currentNode].take + memo[v].dontTake, // i take myself but i dont take you
				memo[currentNode].dontTake + memo[v].take // i dont take myself but i take you
			);
			memo[currentNode].dontTake += memo[v].dontTake; // if i dont take myself and i dont take u, then that means theres some other way
		}
	}

	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: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31