Submission #1108684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108684		Ariadna	Friend (IOI14_friend)	C++14	46 / 100	40 ms	9592 KiB

friend

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

vector<int> dp0, dp1;

int dfs1(int u, int p, vector<vector<int>>& adj, vector<int>& conf);
int dfs0(int u, int p, vector<vector<int>>& adj, vector<int>& conf) {
    if (dp0[u] != -1) return dp0[u];
    dp0[u] = 0;
    for (int v: adj[u]) {
        if (v == p) continue;
        dp0[u] += max(dfs0(v, u, adj, conf), dfs1(v, u, adj, conf));
    }
    return dp0[u];
}

int dfs1(int u, int p, vector<vector<int>>& adj, vector<int>& conf) {
    if (dp1[u] != -1) return dp1[u];
    dp1[u] = conf[u];
    for (int v: adj[u]) {
        if (v == p) continue;;
        dp1[u] += dfs0(v, u, adj, conf);
    }
    return dp1[u];
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    if (n <= 20) {
        vector<vector<int>> adj(n, vector<int>(n, 0));
        for (int i = 1; i < n; ++i) {
            if (protocol[i] == 0 || protocol[i] == 2) 
                adj[host[i]][i] = adj[i][host[i]] = 1;
            if (protocol[i] == 1 || protocol[i] == 2) {
                for (int j = 0; j < n; ++j) {
                    if (adj[j][host[i]]) adj[i][j] = adj[j][i] = 1;
                }
            }
        }

        int ans = 0;
        vector<int> c((1<<n), 0);
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int mask = q.front();
            q.pop();
            for (int i = 0; i < n; ++i) {
                if (mask&(1<<i)) continue;
                bool ok = true;
                for (int j = 0; j < n && ok; ++j) {
                    if (j == i) continue;
                    if (mask&(1<<j) && adj[i][j]) ok = false;
                }
                if (ok) {
                    c[mask|(1<<i)] = c[mask]+confidence[i];
                    ans = max(ans, c[mask|(1<<i)]);
                    q.push(mask|(1<<i));
                }
            }
        }
        return ans;
    }

    vector<vector<int>> adj(n);
    bool b0 = true, b1 = true, b2 = true;
    for (int i = 1; i < n; ++i) {
        if (protocol[i] == 0) b1 = b2 = false;
        else if (protocol[i] == 1) b0 = b2 = false;
        else b0 = b1 = false;
        adj[host[i]].push_back(i);
        adj[i].push_back(host[i]);
    }

    if (b1) {
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += confidence[i];
        return ans;
    } 
    if (b2) {
        int ans = 0;
        for (int i = 0; i < n; ++i) ans = max(ans, confidence[i]);
        return ans;
    }

    dp0 = dp1 = vector<int>(n, -1);
    vector<int> conf(n);
    for (int i = 0; i < n; ++i) conf[i] = confidence[i];

    return max(dfs0(0, 0, adj, conf), dfs1(0, 0, adj, conf));
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:65:10: warning: variable 'b0' set but not used [-Wunused-but-set-variable]
   65 |     bool b0 = true, b1 = true, b2 = true;
      |          ^~

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