제출 #588197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588197		dxz05	친구 (IOI14_friend)	C++14	46 / 100	24 ms	2944 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);
}

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

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

    vector<int> comp;
    function<bool(int, int)> dfs = [&](int v, int x){
        color[v] = x;
        comp.push_back(v);
        for (int u : g[v]){
            if (color[u] == -1 && dfs(u, x ^ 1)) return true;
            if (color[u] == x) return false;
        }
        return false;
    };

    int ans = 0;
    for (int i = 0; i < n; i++){
        if (color[i] == -1){
            comp.clear();
            dfs(i, 0);
            int black = 0, white = 0;
            for (int x : comp){
                // cout << x << ' ';
                if (color[x] == 0){
                    white += val[x];
                } else {
                    black += val[x];
                }
            }
            // cout << endl << endl;
            ans += max(black, white);
        }
    }

    return ans;
}

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: 0 / 23
• Subtask 6: 0 / 31