Submission #1183125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183125		burgerguy	Friend (IOI14_friend)	C++20	100 / 100	16 ms	2120 KiB

friend

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

using namespace std;
using ll = long long;

int findSample(int n, int conf[], int host[], int p[]) {
    vector<int> choose(n), notChoose(n);

    for (int i = 0; i < n; ++i) {
        choose[i] = conf[i];
        notChoose[i] = 0;
    }

    for (int i = n - 1; i > 0; --i) {
        int hostNode = host[i];
        int newNode = i;

        if(p[i] == 0) { // IAmYourFriend
            // Take hostNode/newNode/none
            choose[hostNode] = choose[hostNode] + notChoose[newNode];
            notChoose[hostNode] = max(notChoose[hostNode] + choose[newNode], notChoose[hostNode] + notChoose[newNode]);
        }
        else if(p[i] == 1) { // MyFriendsAreYourFriends
            // Take hostNode/newNode/both/none
            choose[hostNode] = max(max(choose[hostNode] + notChoose[newNode], notChoose[hostNode] + choose[newNode]), choose[hostNode] + choose[newNode]);
            notChoose[hostNode] = notChoose[hostNode] + notChoose[newNode];
        }
        else { //WeAreYourFriends
            // Take hostNode/newNode/none
            choose[hostNode] = max(choose[hostNode] + notChoose[newNode], notChoose[hostNode] + choose[newNode]);
            notChoose[hostNode] = notChoose[hostNode] + notChoose[newNode];
        }
    }

    return max(choose[0], notChoose[0]);
}

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