Submission #598722

#	Time	Username	Problem	Language	Result	Execution time	Memory
598722		dxz05	Friend (IOI14_friend)	C++14	69 / 100	21 ms	2616 KiB

friend

#include "bits/stdc++.h"
#include "friend.h"

using namespace std;

const int MAXN = 100100;

int n, val[MAXN], root[MAXN], type[MAXN];

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define all(x) (x).begin(), (x).end()

vector<vector<int>> get_graph(){
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        if (type[i] == 0) {
            g[i].push_back(root[i]);
            g[root[i]].push_back(i);
        }
        if (type[i] == 1) {
            for (int j : g[root[i]]) {
                if (j == root[i]) continue;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
        if (type[i] == 2) {
            g[i].push_back(root[i]);
            g[root[i]].push_back(i);
            for (int j : g[root[i]]) {
                if (j == root[i]) continue;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    return g;
}

int Subtask1(){
    vector<vector<int>> g = get_graph();
    vector<vector<int>> gg(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) gg[i][j] = 1;
    }

    int ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> vec;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;
            vec.push_back(i);
            cur += val[i];
        }

        bool ok = true;
        for (int i : vec) {
            for (int j : vec) {
                if (i != j && gg[i][j]) ok = false;
            }
        }

        if (ok) ans = max(ans, cur);
    }

    return ans;
}

int Subtask2(){
    return accumulate(val, val + n, 0);
}

int Subtask3(){
    vector<int> p(n);
    iota(all(p), 0);

    function<int(int)> find = [&](int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    };

    function<void(int, int)> unite = [&](int x, int y){
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rng() & 1) swap(x, y);
        p[x] = y;
    };

    for (int i = 1; i < n; i++){
        unite(root[i], i);
    }

    map<int, int> mp;
    for (int i = 0; i < n; i++){
        int x = find(i);
        mp[x] = max(mp[x], val[i]);
    }

    int ans = 0;
    for (auto now : mp) ans += now.second;

    return ans;
}

int Subtask4(){
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++){
        g[i].push_back(root[i]);
        g[root[i]].push_back(i);
    }

    function<pair<int, int>(int, int)> dfs = [&](int v, int p){
        pair<int, int> res = make_pair(val[v], 0);
        for (int u : g[v]){
            if (u == p) continue;
            pair<int, int> dp = dfs(u, v);
            res.first += dp.second;
            res.second += max(dp.first, dp.second);
        }
        return res;
    };

    pair<int, int> ans = dfs(1, 1);
    return max(ans.first, ans.second);
}

struct bipartite_graph {
    int n, m;
    vector<vector<int>> g;

    void init(int _n, int _m) {
        n = _n;
        m = _m;
        g.resize(n + m);
    }

    void init(const vector<vector<int>> &_g) {
        g = _g;
    }

    void add_edge(int u, int v) {
        g[u].push_back(n + v);
    }

    vector<int> max_matching() {
        vector<int> mt(n + m, -1);

        vector<bool> used;
        function<bool(int)> dfs = [&](int v) {
            if (used[v]) return false;
            used[v] = true;
            for (int u : g[v]) {
                if (mt[u] == -1 || dfs(mt[u])) {
                    mt[u] = v;
                    mt[v] = u;
                    return true;
                }
            }
            return false;
        };

        for (int i = 0; i < n; i++) {
            used.assign(n, false);
            dfs(i);
        }

        return mt;
    }

    vector<int> build(int flag) {
        vector<int> mt = max_matching();

        vector<vector<int>> gg(n + m);
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                if (mt[i] == j && mt[j] == i) {
                    gg[j].push_back(i);
                } else {
                    gg[i].push_back(j);
                }
            }
        }

        vector<bool> used(n + m, false);
        vector<int> type(n + m, 0);

        function<void(int)> dfs = [&](int v) {
            used[v] = true;
            type[v] = (v < n ? 1 : 3);
            for (int u : gg[v]) {
                if (!used[u]) dfs(u);
            }
        };

        for (int i = 0; i < n; i++) {
            if (mt[i] == -1 && !used[i]) dfs(i);
        }

        vector<int> Lp, Lm, Rp, Rm;
        for (int i = 0; i < n + m; i++) {
            if (type[i] == 0) type[i] = (i < n ? 2 : 4);
            if (type[i] == 1) Lp.push_back(i);
            if (type[i] == 2) Lm.push_back(i);
            if (type[i] == 3) Rp.push_back(i);
            if (type[i] == 4) Rm.push_back(i);
        }

        vector<int> res;
        if (flag == 1) {  /// vertex cover
            for (int i : Lm) res.push_back(i);
            for (int i : Rp) res.push_back(i);
        } else {  /// independent set
            for (int i : Lp) res.push_back(i);
            for (int i : Rm) res.push_back(i);
        }

        return res;
    }

    vector<int> min_vertex_cover() {
        return build(1);
    }

    vector<int> max_independent_set() {
        return build(2);
    }
};


int Subtask5(){
    vector<vector<int>> g = get_graph();

    vector<int> color(n, 0);    
    function<void(int, int)> dfs = [&](int v, int x){
        color[v] = x;
        for (int u : g[v]){
            if (color[u] == 0) dfs(u, x ^ 3);
        }
    };

    vector<int> id(n, -1);

    int nn = 0, mm = 0;
    for (int i = 0; i < n; i++){
        if (color[i] == 0) dfs(i, 1);
        if (color[i] == 1) id[i] = nn++;
        if (color[i] == 2) id[i] = mm++;
    }

    bipartite_graph bg;
    bg.init(nn, mm);

    for (int i = 0; i < n; i++){
        for (int j : g[i]){
            if (color[i] == 1){
                bg.add_edge(id[i], id[j]);
            } else {
                bg.add_edge(id[j], id[i]);
            }
        }
    }

    return bg.max_independent_set().size();
}

int findSample(int _n, int _val[], int _host[], int _type[]){
    n = _n;
    for (int i = 0; i < n; i++) val[i] = _val[i], root[i] = _host[i], type[i] = _type[i];

    bool IAm = count(type + 1, type + n, 0) > 0;
    bool MyFriends = count(type + 1, type + n, 1) > 0;
    bool WeAre = count(type + 1, type + n, 2) > 0;

    if (n <= 10) return Subtask1();
    if (!IAm && MyFriends && !WeAre) return Subtask2();
    if (!IAm && !MyFriends && WeAre) return Subtask3();
    if (IAm && !MyFriends && !WeAre) return Subtask4();
    if (!WeAre && *max_element(val, val + n) == 1) return Subtask5();

    return -1;
}

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