Submission #1168932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168932		anmattroi	Friend (IOI14_friend)	C++17	11 / 100	210 ms	131072 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

int f[1024], s[1024];

vector<int> adj[maxn];

int findSample(int n, int confidence[], int host[], int protocol[]){
    for (int i = 0; i < (1<<n); i++) f[i] = s[i] = 0;
    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 1; i < n; i++) {
        switch (protocol[i]) {
        case 0 :
            adj[host[i]].emplace_back(i);
            adj[i].emplace_back(host[i]);
            break;
        case 1 :
            for (int v : adj[host[i]]) {
                adj[v].emplace_back(i);
                adj[i].emplace_back(v);
            }
            break;
        default :

            for (int v : adj[host[i]]) {
                adj[v].emplace_back(i);
                adj[i].emplace_back(v);
            }
            adj[host[i]].emplace_back(i);
            adj[i].emplace_back(host[i]);
        }
    }
    for (int i = 0; i < n; i++)
        for (int j : adj[i]) {
            f[(1<<i)|(1<<j)] = 1;
            int mask = ((1<<i)|(1<<j));
        }

    for (int i = 0; i < n; i++) for (int mask = 0; mask < (1<<n); mask++) if (mask>>i&1) f[mask] += f[mask^(1<<i)];



    int ans = 0;
    for (int i = 1; i < (1<<n); i++) {
        s[i] = s[i-(i&-i)] + confidence[__lg(i&-i)];
        f[i] ? 0 : ans = max(ans, s[i]);
    }
    return ans;
}
/*
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
*/

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