Submission #576148

#	Time	Username	Problem	Language	Result	Execution time	Memory
576148		elazarkoren	Friend (IOI14_friend)	C++17	46 / 100	33 ms	15524 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;

int n;

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

pii Solve(vvi &tree, int node, int parent) {
    int x = a[node], y = 0;
    for (int neighbor : tree[node]) {
        if (neighbor == parent) continue;
        auto [x1, y1] = Solve(tree, neighbor, node);
        x += y1, y += x1;
    }
    chkmax(x, y);
    return {x, y};
}

int color[MAX_N];

int findSample(int N, int confidence[], int host[], int protocol[]) {
    n = N;
    bool subtask2 = true, subtask3 = true, subtask4 = true;
    for (int i = 0; i < n; i++) a[i] = confidence[i];
    if (*max_element(a, a + n) == 1) {
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (!protocol[i]) {
                color[i] = 1 - color[host[i]];
            } else color[i] = color[host[i]];
            ans += color[i];
        }
        return max(ans, n - ans);
    }
    vvi tree(n);
    for (int i = 1; i < n; i++) {
        if (protocol[i] != 1) subtask2 = false;
        if (protocol[i] != 2) subtask3 = false;
        if (protocol[i]) subtask4 = 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) {
            tree[i].push_back(host[i]);
            tree[host[i]].push_back(i);
            graph[host[i]][i] = graph[i][host[i]] = 1;
        }
    }
    if (subtask2) {
        int s = 0;
        for (int i = 0; i < n; i++) s += a[i];
        return s;
    }
    if (subtask3) {
        return *max_element(a, a + n);
    }
    if (subtask4) {
        return Solve(tree, 0, -1).x;
    }
    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: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31