Submission #623441

#	Time	Username	Problem	Language	Result	Execution time	Memory
623441		yuto1115	Friend (IOI14_friend)	C++17	69 / 100	188 ms	65536 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) int(a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class dinic {
    struct edge {
        int cap, to, rev;
    };
    int n;
    vector<vector<edge>> G;
    vi dist, iter;
    
    void bfs(int s) {
        dist.assign(n, inf);
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        while (not q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &e: G[u]) {
                if (!e.cap) continue;
                if (chmin(dist[e.to], dist[u] + 1)) q.push(e.to);
            }
        }
    }
    
    int dfs(int u, int t, int f) {
        if (u == t) {
            assert(f);
            return f;
        }
        for (int &i = iter[u]; i < SZ(G[u]); ++i) {
            auto &e = G[u][i];
            if (dist[e.to] != dist[u] + 1) continue;
            if (!e.cap) continue;
            int now = dfs(e.to, t, min(f, e.cap));
            if (!now) continue;
            e.cap -= now;
            G[e.to][e.rev].cap += now;
            return now;
        }
        return 0;
    }

public:
    dinic(int n) : n(n), G(n) {}
    
    void add_edge(int u, int v, int c) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        assert(u != v);
        G[u].pb({c, v, SZ(G[v])});
        G[v].pb({0, u, SZ(G[u]) - 1});
    }
    
    int max_flow(int s, int t) {
        assert(0 <= s and s < n);
        assert(0 <= t and t < n);
        assert(s != t);
        int res = 0;
        while (true) {
            bfs(s);
            if (dist[t] == inf) break;
            iter.assign(n, 0);
            int f;
            while (f = dfs(s, t, inf), f) {
                res += f;
            }
        }
        return res;
    }
};

// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[]) {
    if (n <= 10) {
        vvb G(n, vb(n));
        rep2(nx, 1, n) {
            int i = host[nx];
            if (protocol[nx] != 1) G[i][nx] = G[nx][i] = true;
            if (protocol[nx] != 0) {
                rep(j, nx) {
                    if (!G[i][j]) continue;
                    G[j][nx] = G[nx][j] = true;
                }
            }
        }
        int mx = 0;
        rep(bit, 1 << n) {
            bool ok = true;
            rep(i, n) rep(j, n) {
                    if ((bit >> i & 1) and (bit >> j & 1) and G[i][j]) ok = false;
                }
            if (!ok) continue;
            int now = 0;
            rep(i, n) if (bit >> i & 1) now += confidence[i];
            chmax(mx, now);
        }
        return mx;
    } else if (*min_element(protocol + 1, protocol + n) == *max_element(protocol + 1, protocol + n)) {
        if (protocol[1] == 0) {
            vvi G(n);
            rep2(i, 1, n) {
                G[i].pb(host[i]);
                G[host[i]].pb(i);
            }
            auto dfs = [&](auto &dfs, int u, int p) -> P {
                P res(0, confidence[u]);
                for (int v: G[u]) {
                    if (v == p) continue;
                    P now = dfs(dfs, v, u);
                    res.first += max(now.first, now.second);
                    res.second += now.first;
                }
                return res;
            };
            P ans = dfs(dfs, 0, -1);
            return max(ans.first, ans.second);
        } else if (protocol[1] == 1) {
            return accumulate(confidence, confidence + n, 0);
        } else {
            return *max_element(confidence, confidence + n);
        }
    } else {
        vvi G(n);
        vi c(n);
        rep2(i, 1, n) {
            if (protocol[i] == 0) {
                G[host[i]].pb(i);
                G[i].pb(host[i]);
                c[i] = 1 - c[host[i]];
            } else {
                for (int j: G[host[i]]) {
                    G[j].pb(i);
                    G[i].pb(j);
                }
                c[i] = c[host[i]];
            }
        }
        dinic dc(n + 2);
        int s = n, t = n + 1;
        rep(i, n) {
            if (c[i]) {
                dc.add_edge(s, i, 1);
                for (int j: G[i]) {
                    assert(!c[j]);
                    dc.add_edge(i, j, 1);
                }
            } else {
                dc.add_edge(i, t, 1);
            }
        }
        return n - dc.max_flow(s, t);
    }
}

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