Submission #587981

#	Time	Username	Problem	Language	Result	Execution time	Memory
587981		dxz05	Friend (IOI14_friend)	C++14	19 / 100	22 ms	1364 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) > 0;
    bool MyFriends = count(type, type + n, 1) > 0;
    bool WeAre = count(type, type + n, 2) > 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 accumulate(val, val + n, 0);
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:7:10: warning: unused variable 'IAm' [-Wunused-variable]
    7 |     bool IAm = count(type, type + n, 0) > 0;
      |          ^~~
friend.cpp:8:10: warning: unused variable 'MyFriends' [-Wunused-variable]
    8 |     bool MyFriends = count(type, type + n, 1) > 0;
      |          ^~~~~~~~~
friend.cpp:9:10: warning: unused variable 'WeAre' [-Wunused-variable]
    9 |     bool WeAre = count(type, type + n, 2) > 0;
      |          ^~~~~

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