Submission #1064108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064108		VMaksimoski008	Friend (IOI14_friend)	C++17	46 / 100	25 ms	3920 KiB

friend

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

int mat[10][10];
vector<int> graph[1005];
int dp[1005][2], C[1005];

void dfs(int u, int p) {
    dp[u][1] = C[u];

    for(int &v : graph[u]) {
        if(v == p) continue;
        dfs(v, u);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
	int ans=0;
    for(int i=0; i<n; i++) C[i] = confidence[i];

    if(n <= 10) {
        for(int i=1; i<n; i++) {
            if(protocol[i] == 0) {
                mat[host[i]][i] = mat[i][host[i]] = 1;
            } else if(protocol[i] == 1) {
                for(int j=0; j<n; j++)
                    if(mat[host[i]][j]) mat[i][j] = mat[j][i] = 1;
            } else {
                mat[host[i]][i] = mat[i][host[i]] = 1;
                for(int j=0; j<n; j++)
                    if(mat[host[i]][j]) mat[i][j] = mat[j][i] = 1;
            }
        }

        for(int s=0; s<(1<<n); s++) {
            bool ok = 1;
            vector<int> vec;
            for(int i=0; i<n; i++) {
                if(s & (1 << i)) {
                    for(int &x : vec) if(mat[x][i]) ok = 0;
                    vec.push_back(i);
                }
            }

            if(ok) {
                int sum = 0;
                for(int &x : vec) sum += confidence[x];
                ans = max(ans, sum);
            }
        }
        return ans;
    }

    set<int> st;
    for(int i=1; i<n; i++) st.insert(protocol[i]);

    if(st.size() == 1 && *st.begin() == 1) {
        for(int i=0; i<n; i++) ans += confidence[i];
        return ans;
    }

    if(st.size() == 1 && *st.begin() == 2) {
        for(int i=0; i<n; i++) ans = max(ans, confidence[i]);
        return ans;
    }

    if(st.size() == 1 && *st.begin() == 0) {
        for(int i=1; i<n; i++) {
            graph[host[i]].push_back(i);
            graph[i].push_back(host[i]);
        }

        dfs(0, 0);
        return max(dp[0][0], dp[1][0]);
    }

	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