Submission #367492

#	Time	Username	Problem	Language	Result	Execution time	Memory
367492		KoD	Friend (IOI14_friend)	C++17	69 / 100	72 ms	65540 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(std::max(begin, end)) { }
    itr begin() const { return first; }
    itr end() const { return last; }
};

constexpr int INF = 1000000000;

struct MaxFlow {
    struct Edge {
        int to, cap, rev;
    };
    Vec<Vec<Edge>> graph;
    Vec<char> done;
    MaxFlow(const int n): graph(n), done(n) { }

    void addEdge(const int u, const int v, const int c) {
        // std::cout << u << ' ' << v << '\n';
        graph[u].push_back(Edge { v, c, (int) graph[v].size() });
        graph[v].push_back(Edge { u, 0, (int) graph[u].size() - 1 });
    }

    int dfs(const int cur, const int dst, const int push) {
        if (done[cur]) {
            return 0;
        }
        done[cur] = true;
        if (cur == dst) {
            return push;
        }
        for (auto &e: graph[cur]) {
            if (e.cap > 0) {
                const auto tmp = dfs(e.to, dst, std::min(push, e.cap));
                if (tmp > 0) {
                    e.cap -= tmp;
                    graph[e.to][e.rev].cap += tmp;
                    return tmp;
                }
            }
        }
        return 0;
    }

    int maxFlow(const int src, const int dst) {
        int ret = 0;
        while (true) {
            const auto push = dfs(src, dst, INF);
            if (push == 0) {
                break;
            }
            ret += push;
            std::fill(done.begin(), done.end(), 0);
        }
        return ret;
    }
};

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 = confidence[u], 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);
    }
    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;
        }
    }
    if (n <= 10) {
        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;
    }
    Vec<int> col(n);
    auto dfs = [&](auto dfs, const int u, const int c) -> void {
        if (col[u] != 0) {
            return;
        }
        col[u] = c;
        for (const auto v: range(0, n)) {
            if (graph[u][v]) {
                dfs(dfs, v, -c);
            }
        }
    };
    for (const auto src: range(0, n)) {
        if (col[src] == 0) {
            dfs(dfs, src, 1);
        }
    }
    MaxFlow flow(n + 2);
    for (const auto u: range(0, n)) {
        if (col[u] == 1) {
            flow.addEdge(n, u, 1);
        }
        else {
            flow.addEdge(u, n + 1, 1);
        }
    }
    for (const auto u: range(0, n)) {
        if (col[u] == 1) {
            for (const auto v: range(0, n)) {
                if (graph[u][v]) {
                    flow.addEdge(u, v, 1);
                }
            }
        }
    }
    return n - flow.maxFlow(n, n + 1);
}

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