oj.uz

Submission #316304

# Submission time Handle Problem Language Result Execution time Memory
316304 2020-10-25T19:43:29 Z qpwoeirut Friend (IOI14_friend) C++17
46 / 100
 42 ms 7416 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 4 ms 5120 KB Output is correct
15 Correct 3 ms 4992 KB Output is correct
16 Correct 4 ms 4992 KB Output is correct
17 Correct 3 ms 4992 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 5152 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 3 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Correct 4 ms 5120 KB Output is correct
14 Correct 4 ms 4992 KB Output is correct
15 Correct 4 ms 5120 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 4 ms 5248 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Incorrect 3 ms 4992 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Incorrect 42 ms 7416 KB Output isn't correct
13 Halted 0 ms 0 KB -