Submission #367743

#	Time	Username	Problem	Language	Result	Execution time	Memory
367743		KoD	Friend (IOI14_friend)	C++17	100 / 100	42 ms	3436 KiB

friend

#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <utility>

#ifndef LOCAL
#include "friend.h"
#endif

template <class T>
using Vec = std::vector<T>;

int findSample(int n, int confidence[], int host[], int protocol[]) {
    Vec<int> take(n), ignore(n);
    for (int i = 0; i < n; ++i) {
        take[i] = confidence[i];
    }
    for (int i = n - 1; i >= 1; --i) {
        const auto u = host[i];
        const auto v = i;
        const auto p = protocol[i];
        if (p == 0) {
            const auto tk = take[u] + ignore[v];
            const auto ig = ignore[u] + std::max(take[v], ignore[v]);
            take[u] = tk;
            ignore[u] = ig;
        }
        else if (p == 1) {
            const auto tk = std::max(take[u] + std::max(take[v], ignore[v]), ignore[u] + take[v]);
            const auto ig = ignore[u] + ignore[v];
            take[u] = tk;
            ignore[u] = ig;
        }
        else {
            const auto tk = std::max(take[u] + ignore[v], ignore[u] + take[v]);
            const auto ig = ignore[u] + ignore[v];
            take[u] = tk;
            ignore[u] = ig;
        }
    }
    return std::max(take[0], ignore[0]);
}

#ifdef LOCAL 
int main() {
    int n;
    std::cin >> n;
    int cf[100] = {};
    for (int i = 0; i < n; ++i) {
        std::cin >> cf[i];
    }
    int host[100] = {};
    int prot[100] = {};
    for (int i = 1; i < n; ++i) {
        std::cin >> host[i] >> prot[i];
    }
    std::cout << findSample(n, cf, host, prot) << '\n';
    return 0;
}   
#endif

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