Submission #298748

#	Time	Username	Problem	Language	Result	Execution time	Memory
298748		juckter	Friend (IOI14_friend)	C++14	100 / 100	38 ms	3448 KiB

friend

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

// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[]) {
    vector<int> dp0(n), dp1(n);
    
    for(int i = 0; i < n; i++)
        dp1[i] = confidence[i];

    for(int v = n - 1; v >= 1; v--) {
        int u = host[v];
        if(protocol[v] == 0) {
            dp1[u] = dp1[u] + dp0[v];
            dp0[u] = dp0[u] + max(dp0[v], dp1[v]);
        }
        if(protocol[v] == 1) {
            dp1[u] = max({dp1[u] + dp1[v], dp1[u] + dp0[v], dp0[u] + dp1[v]});
            dp0[u] += dp0[v];
        }
        if(protocol[v] == 2) {
            dp1[u] = max(dp1[u] + dp0[v], dp0[u] + dp1[v]);
            dp0[u] += dp0[v];
        }
    }
    return max(dp0[0], dp1[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