Submission #1241855

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

friend

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef long long ll ;
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vull vector<ull>
#define vb vector<bool>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvpii vector<vpii>
#define f(i,x,n) for(int i=x;i<n;i++)
#define fe(i,x,n) for (int i=x;i<=n;i++)
#define fr(i,x,n) for (int i=x;i>n;i--)
#define fre(i,x,n) for(int i=x;i>=n;i--)
#define fll(i,x,n) for (ll i=x;i<n;i++)

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