Submission #588026

#	Time	Username	Problem	Language	Result	Execution time	Memory
588026		dxz05	Friend (IOI14_friend)	C++14	16 / 100	2 ms	344 KiB

friend

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

using namespace std;

const int MAXN = 100100;

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

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

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

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

    vector<vector<int>> gg(n, vector<int>(n, 0));
    // cout << "\nedges\n";
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) gg[i][j] = 1;
        // for (int j : g[i]) cout << i << ' ' << j << endl;
    }
    // cout << "\nedges\n";

    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(person[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 findSample(int _n, int _val[], int _person[], int _type[]){
    n = _n;
    for (int i = 0; i < n; i++) val[i] = _val[i], person[i] = _person[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) Subtask1();
    if (!IAm && MyFriends && !WeAre) return Subtask2();
    if (!IAm && !MyFriends && WeAre) return Subtask3();

    return -1;
}

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