Submission #576133

#	Time	Username	Problem	Language	Result	Execution time	Memory
576133		elazarkoren	Friend (IOI14_friend)	C++17	27 / 100	25 ms	4348 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1001;

//vi graph[MAX_N];
int graph[MAX_N][MAX_N];

int findSample(int n, int confidence[], int host[], int protocol[]) {
    bool subtask2 = true, subtask3 = true;
    for (int i = 1; i < n; i++) {
        if (protocol[i] != 1) subtask2 = false;
        if (protocol[i] != 2) subtask3 = false;
        if (protocol[i]) {
            for (int j = 0; j < n; j++) {
                if (graph[host[i]][j]) {
                    graph[i][j] = graph[j][i] = 1;
                }
            }
        }
        if (protocol[i] != 1) {
            graph[host[i]][i] = graph[i][host[i]] = 1;
        }
    }
    if (subtask2) {
        int s = 0;
        for (int i = 0; i < n; i++) {
            s += confidence[i];
        }
        return s;
    }
    if (subtask3) {
        return *max_element(confidence, confidence + n);
    }
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        int mask = i;
        vi v;
        while (mask) {
            v.push_back(__builtin_ctz(mask));
            mask -= mask & (-mask);
        }
        bool b = true;
        int curr = 0;
        for (int i : v) {
            for (int j : v) {
                if (graph[i][j]) {
                    b = false;
                    break;
                }
            }
            if (!b) break;
            curr += confidence[i];
        }
        if (b) chkmax(ans, curr);
    }
    return ans;
}

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