Submission #550097

#	Time	Username	Problem	Language	Result	Execution time	Memory
550097		tabr	Friend (IOI14_friend)	C++17	69 / 100	185 ms	65536 KiB

friend

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct matching {
    vector<vector<int>> g;
    vector<int> pa;
    vector<int> pb;
    vector<int> was;
    int n, m;
    int res;
    int iter;

    matching(int _n, int _m) : n(_n), m(_m) {
        pa.assign(n, -1);
        pb.assign(m, -1);
        was.resize(n);
        g.resize(n);
        res = 0;
        iter = 0;
    }

    void add(int from, int to) {
        g[from].emplace_back(to);
    }

    bool dfs(int v) {
        was[v] = iter;
        for (int u : g[v]) {
            if (pb[u] == -1) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        for (int u : g[v]) {
            if (was[pb[u]] != iter && dfs(pb[u])) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        return false;
    }

    int solve() {
        while (true) {
            iter++;
            int add = 0;
            for (int i = 0; i < n; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    add++;
                }
            }
            if (add == 0) {
                break;
            }
            res += add;
        }
        return res;
    }
};

int findSample(int n, int c[], int h[], int p[]) {
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        if (p[i] != 0) {
            for (int j : g[h[i]]) {
                g[i].emplace_back(j);
                g[j].emplace_back(i);
            }
        }
        if (p[i] != 1) {
            g[i].emplace_back(h[i]);
            g[h[i]].emplace_back(i);
        }
    }
    if (all_of(p + 1, p + n, [&](int x) { return (x == 1); })) {
        return accumulate(c, c + n, 0);
    } else if (all_of(p + 1, p + n, [&](int x) { return (x == 2); })) {
        return *max_element(c, c + n);
    } else if (all_of(p + 1, p + n, [&](int x) { return (x == 0); })) {
        vector<vector<int>> dp(n, vector<int>(2));
        function<void(int)> Dfs = [&](int v) {
            dp[v][1] = c[v];
            for (int to : g[v]) {
                if (dp[to][1] != 0) {
                    continue;
                }
                Dfs(to);
                dp[v][0] += max(dp[to][0], dp[to][1]);
                dp[v][1] += dp[to][0];
            }
        };
        Dfs(0);
        return max(dp[0][0], dp[0][1]);
    } else if (all_of(c, c + n, [&](int x) { return (x == 1); }) && all_of(p + 1, p + n, [&](int x) { return (x <= 1); })) {
        vector<int> depth(n);
        function<void(int)> Dfs = [&](int v) {
            for (int to : g[v]) {
                if (depth[to] != 0) {
                    continue;
                }
                depth[to] = depth[v] + 1;
                Dfs(to);
            }
        };
        for (int i = 0; i < n; i++) {
            if (depth[i] != 0) {
                continue;
            }
            Dfs(i);
        }
        matching mt(n, n);
        for (int i = 0; i < n; i++) {
            if (depth[i] % 2 == 1) {
                continue;
            }
            for (int j : g[i]) {
                mt.add(i, j);
            }
        }
        return n - mt.solve();
    } else {
        assert(n <= 10);
        int ans = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int t = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    t += c[i];
                    for (int j : g[i]) {
                        if (mask & (1 << j)) {
                            t = (int) -1e9;
                            break;
                        }
                    }
                }
            }
            ans = max(ans, t);
        }
        return ans;
    }
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    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