Submission #367465

#	Time	Username	Problem	Language	Result	Execution time	Memory
367465		KoD	친구 (IOI14_friend)	C++17	16 / 100	1 ms	512 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::count(protocol + 1, protocol + n, 0) == n - 1) {
        Vec<Vec<int>> children(n);
        for (const auto i: range(1, n)) {
            children[host[i]].push_back(i);
        }
        auto dfs = [&](auto dfs, const int u) -> std::pair<int, int> {
            int use = 1, avoid = 0;
            for (const auto v: children[u]) {
                const auto [u, a] = dfs(dfs, v);
                avoid += std::max(u, a);
                use += a;
            }
            return std::make_pair(use, avoid);
        };
        const auto [u, a] = dfs(dfs, 0);
        return std::max(u, a);
    }
    if (std::count(protocol + 1, protocol + n, 1) == n - 1) {
        return std::accumulate(confidence, confidence + n, 0);
    }
    if (std::count(protocol + 1, protocol + n, 2) == n - 1) {
        return *std::max_element(confidence, confidence + n);
    }
    if (n <= 10) {
        Vec<Vec<char>> graph(n, Vec<char>(n));
        for (const auto v: range(1, n)) {
            const auto u = host[v];
            if (protocol[v] != 0) {
                for (const auto w: range(0, n)) {
                    if (w != v) {
                        if (graph[u][w]) {
                            graph[v][w] = 1;
                            graph[w][v] = 1;
                        }
                    }
                }
            }
            if (protocol[v] != 1) {
                graph[u][v] = 1;
                graph[v][u] = 1;
            }
        }
        int ret = 0;
        for (const auto set: range(0, 1 << n)) {
            int sum = 0;
            bool ok = true;
            for (const auto i: range(0, n)) {
                if (set >> i & 1) {
                    sum += confidence[i];
                    for (const auto j: range(0, n)) {
                        if (set >> j & 1) {
                            if (graph[i][j]) {
                                ok = false;
                            }
                        }
                    }
                }
            }
            if (ok) {
                ret = std::max(ret, sum);
            }
        }
        return ret;
    }
    return 0;
}

#ifdef LOCAL 
int main() {
    int n;
    std::cin >> n;
    int cf[100] = {};
    for (const auto i: range(0, n)) {
        std::cin >> cf[i];
    }
    int host[100] = {};
    int prot[100] = {};
    for (const auto i: range(1, n)) {
        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