Submission #316304

#	Time	Username	Problem	Language	Result	Execution time	Memory
316304		qpwoeirut	Friend (IOI14_friend)	C++17	46 / 100	42 ms	7416 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;

const int MN = 100001;
set<int> adj[MN];

void construct(int n, int host[], int protocol[]) {
    for (int i=1; i<n; ++i) {
        int u = host[i];
        if (protocol[i] == 0 || protocol[i] == 2) {
            adj[u].insert(i);
            adj[i].insert(u);
        }
        if (protocol[i] == 1 || protocol[i] == 2) {
            for (auto it=adj[u].begin(); it!=adj[u].end(); ++it) {
                adj[*it].insert(i);
                adj[i].insert(*it);
            }
        }
    }
}

int solve1(int n, int confidence[], int host[], int protocol[]) {
    construct(n, host, protocol);
    int ans = 0;
    for (int mask=0; mask<(1 << n); ++mask) {
        bool ok = true;
        for (int u=0; u<n; ++u) {
            if (((mask >> u) & 1) == 0) continue;
            for (int v=u+1; v<n; ++v) {
                if (((mask >> v) & 1) == 0) continue;

                if (adj[u].count(v)) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            int sum = 0;
            for (int i=0; i<n; ++i) {
                if ((mask >> i) & 1) {
                    sum += confidence[i];
                }
            }
            ans = max(ans, sum);
            //for (int i=0; i<n; ++i) { if ((mask >> i) & 1) { cerr << i << ' '; } }cerr << endl;
        }
    }

    return ans;
}

int solve2(int n, int confidence[], int host[], int protocol[]) {
    int sum = 0;
    for (int i=0; i<n; ++i) {
        sum += confidence[i];
    }
    return sum;
}

int solve3(int n, int confidence[], int host[], int protocol[]) {
    int ans = 0;
    for (int i=0; i<n; ++i) {
        ans = max(ans, confidence[i]);
    }
    return ans;
}

bool visited[MN];
int dp[MN][2];
void dfs(int node, int par, int conf[]) {
    visited[node] = true;
    dp[node][0] = 0;
    dp[node][1] = conf[node];

    for (auto it=adj[node].begin(); it!=adj[node].end(); ++it) {
        if (*it == par) continue;
        dfs(*it, node, conf);

        dp[node][0] += max(dp[*it][0], dp[*it][1]);
        dp[node][1] += dp[*it][0];
    }
}

int solve4(int n, int confidence[], int host[], int protocol[]) {
    construct(n, host, protocol);
    fill(visited, visited+n, false);
    int ans = 0;
    for (int i=0; i<n; ++i) {
        if (!visited[i]) {
            dfs(i, -1, confidence);
            ans += max(dp[i][0], dp[i][1]);
        }
    }
    return ans;
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    if (n <= 10) {
        return solve1(n, confidence, host, protocol);
    } else if (protocol[1] == 1) {
        return solve2(n, confidence, host, protocol);
    } else if (protocol[1] == 2) {
        return solve3(n, confidence, host, protocol);
    } else if (protocol[1] == 0) {
        return solve4(n, confidence, host, protocol);
    } else {
        return 8;
    }
}

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