Submission #1241856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241856		coderg	Friend (IOI14_friend)	C++20	100 / 100	16 ms	2964 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef long long ll ;


int findSample(int n, int confidence[], int host[], int protocol[]) {
    ll select[n], hola[n];

    for(ll i=0;i<n;i++) {
        select[i] = confidence[i];
        hola[i] = 0;    
    }

    for(ll i=n-1;i>=1;i--) {
        ll u = host[i], v = i;

        if(protocol[i] == 0) { // host
            select[u] = select[u] + hola[v];
            hola[u] = max(hola[u] + hola[v], hola[u] + select[v]);
        }else if(protocol[i] == 1) { // friends of host but not the host
            select[u] = max({select[u] + select[v], select[u] + hola[v], hola[u] + select[v]});
            hola[u] = hola[u] + hola[v];
        }else if(protocol[i] == 2) { // friend of host and host
            select[u] = max(select[u] + hola[v], hola[u] + select[v]);
           hola[u] = hola[u] + hola[v];
        }
    }
    return max(select[0], hola[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