Submission #1184351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184351		TroySer	친구 (IOI14_friend)	C++20	27 / 100	0 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);

	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].dontTake, memo[v].take); // you're allowed to do either
		} else if (protocol[i] == 1) {
			memo[currentNode].take += max(memo[v].dontTake, memo[v].take);
			memo[currentNode].dontTake += max(memo[v].dontTake, memo[v].take);
		} else if (protocol[i] == 2) {
			memo[currentNode].take += memo[v].dontTake;
			memo[currentNode].dontTake += max(memo[v].dontTake, memo[v].take);
		}
	}

	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: 0 / 23
• Subtask 6: 0 / 31