Submission #367438

#	Time	Username	Problem	Language	Result	Execution time	Memory
367438		KoD	Friend (IOI14_friend)	C++17	16 / 100	1 ms	620 KiB

friend

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

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

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

struct range {
    struct itr {
        ll i;
        itr(const ll i): i(i) { }
        ll operator * () const { return i; }
        void operator ++ () { i += 1; }
        bool operator != (const itr &other) { return i != other.i; }
    };
    const itr first, last;
    range(const ll begin, const ll end): first(begin), last(end) { }
    itr begin() const { return first; }
    itr end() const { return last; }
};

int findSample(int n, int confidence[], int host[], int protocol[]) {
    if (std::all_of(protocol + 1, protocol + n, [](const int x) { return x < 2; } )) {
        Vec<Vec<std::pair<int, bool>>> graph(n);
        for (int i = 1; i < n; ++i) {
            const bool f = (protocol[i] == 0);
            graph[i].emplace_back(host[i], f);
            graph[host[i]].emplace_back(i, f);
        }
        int ret = 0;
        Vec<int> col(n);
        int a = 0, b = 0;
        auto dfs = [&](auto dfs, const int u, const int c) -> void {
            if (col[u] != 0) {
                return;
            }
            col[u] = c;
            (col[u] == 1 ? a : b) += confidence[u];
            for (const auto [v, f]: graph[u]) {
                dfs(dfs, v, f ? -c : c);
            }
        };
        for (int i = 0; i < n; ++i) {
            if (col[i] == 0) {
                dfs(dfs, i, 1);
                ret += std::max(a, b);
                a = b = 0;
            }
        }
        return ret;
    }
    else {
        return *std::max_element(confidence, confidence + n);
    }
}

#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: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31