Submission #385857

#	Time	Username	Problem	Language	Result	Execution time	Memory
385857		ParsaAlizadeh	Friend (IOI14_friend)	C++17	46 / 100	31 ms	1516 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
 
int Sub1(int n, int confidence[], int host[], int protocol[]) {
    vector<vector<bool>> g(n, vector<bool>(n, false));
    auto add_edge = [&g] (int u, int v) {
        g[u][v] = g[v][u] = true;
    };
    for (int i = 1; i < n; i++) {
        if (protocol[i] == 0 || protocol[i] == 2) {
            add_edge(i, host[i]);
        }
        if (protocol[i] == 1 || protocol[i] == 2) {
            for (int j = 0; j < n; j++) if (g[host[i]][j]) {
                add_edge(j, i);
            }
        }
    }
    int ans = -1;
    for (int mask = 0; mask < (1 << n); mask++) {
        bool flag = true;
        int now = 0;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) {
            now += confidence[i];
            for (int j = i + 1; j < n; j++) if (mask & (1 << j)) {
                flag &= !g[i][j];
            }
        }
        if (!flag)
            continue;
        ans = max(ans, now);
    }
    return ans;
}
 
int Sub2(int n, int confidence[], int host[], int protocol[]) {
    int ans = confidence[0];
    for (int i = 1; i < n; i++) {
        if (protocol[i] != 1)
            return -1;
        ans += confidence[i];
    }
    return ans;
}
 
int Sub3(int n, int confidence[], int host[], int protocol[]) {
    int ans = confidence[0];
    for (int i = 1; i < n; i++) {
        if (protocol[i] != 2)
            return -1;
        ans = max(ans, confidence[i]);
    }
    return ans;
}
 
int Sub4(int n, int confidence[], int host[], int protocol[]) {
    for (int i = 1; i < n; i++) {
        if (protocol[i] != 0)
            return -1;
    }
    vector<vector<int>> adj(n), dp(n, vector<int>(2));
    for (int i = 1; i < n; i++)
        adj[host[i]].push_back(i);
    for (int i = n; i--;) {
        dp[i][1] = confidence[i];
        for (int j : adj[i]) {
            dp[i][0] += dp[j][1];
            dp[i][1] += dp[j][0];
        }
        dp[i][1] = max(dp[i][1], dp[i][0]);
    }
    return dp[0][1];
}
 
int findSample(int n, int confidence[], int host[], int protocol[]){
    int ans = -1;
    if (n <= 10)
        return Sub1(n, confidence, host, protocol);
    if ((ans = Sub2(n, confidence, host, protocol)) != -1)
        return ans;
    if ((ans = Sub3(n, confidence, host, protocol)) != -1)
        return ans;
    if ((ans = Sub4(n, confidence, host, protocol)) != -1)
        return ans;
    return -1;
}

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