Submission #587979

#	Time	Username	Problem	Language	Result	Execution time	Memory
587979		dxz05	Friend (IOI14_friend)	C++14	11 / 100	29 ms	2636 KiB

friend

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

using namespace std;

int findSample(int n, int val[], int host[], int type[]){
    bool IAm = count(type, type + n, 0);
    bool MyFriends = count(type, type + n, 1);
    bool WeAre = count(type, type + n, 2);

    if (MyFriends && !IAm && !WeAre){
        return accumulate(val, val + n, 0);
    }
    
    if (n <= 10){
        vector<vector<int>> g(n);
        for (int i = 1; i < n; i++){
            if (type[i] == 0){
                g[i].push_back(host[i]);
                g[host[i]].push_back(i);
            }
            if (type[i] == 1){
                for (int j : g[host[i]]){
                    if (j == host[i]) continue;
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
            if (type[i] == 2){
                g[i].push_back(host[i]);
                g[host[i]].push_back(i);
                for (int j : g[host[i]]){
                    if (j == host[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;
    }

    return -1;
}

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