oj.uz

Submission #874107

# Submission time Handle Problem Language Result Execution time Memory
874107 2023-11-16T09:17:31 Z dzuizz Friend (IOI14_friend) C++14
46 / 100
 39 ms 10804 KB 
// Subtask 4

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

const int MAXN = 1005;

vector<vector<int> > adjlist;
int memo[MAXN][MAXN][2];

int dfs(int cur, int prev, int k, int confidence[]) {
    if (memo[cur][prev][k]) return memo[cur][prev][k];
    int ans = 0;

    for (auto &nx : adjlist[cur]) {
        if (nx == prev) continue;
        ans += dfs(nx, cur, 1, confidence);
    }

    if (k == 0) return ans;

    int res = confidence[cur];
    for (auto &nx : adjlist[cur]) {
        if (nx == prev) continue;
        res += dfs(nx, cur, 0, confidence);
    }

    return memo[cur][prev][k] = max(ans, res);
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    adjlist.resize(n);

    bool subtask2 = 1, subtask3 = 1, subtask4 = 1;
    for (int i=1; i<n; i++) {
        if (protocol[i] != 1) subtask2 = 0;
        if (protocol[i] != 2) subtask3 = 0;
        if (protocol[i] != 0) subtask4 = 0;
    }

    if (subtask2) {
        int ans=0;
        for (int i=0; i<n; i++) ans += confidence[i];

        return ans;
    }

    if (subtask3) {
        int ans=0;
        for (int i=0; i<n; i++) ans = max(ans, confidence[i]);

        return ans;
    }

    for (int i=1; i<n; i++) {
        if (protocol[i] != 1) {
            adjlist[host[i]].push_back(i);
            adjlist[i].push_back(host[i]);
        }
        if (protocol[i] != 0) {
            for (auto &nx : adjlist[host[i]]) {
                adjlist[i].push_back(nx);
                adjlist[nx].push_back(i);
            }
        }
    }

    if (subtask4) {
        return dfs(0, -1, 1, confidence);
    }

    int ans=0;
    for (int i=0; i<(1<<n); i++) {
        bool vis[n]; memset(vis, 0, sizeof(vis));
        bool flag=1;
        int res=0;
        
        for (int j=0; j<n&&flag; j++) {
            int bit = (i>>j)&1;
            if (bit == 0) continue;
            res += confidence[j];
            
            for (auto &nx : adjlist[j]) if (vis[nx]) flag = 0;
            vis[j] = 1;
        }
        if (flag) ans = max(ans, res);
    }

    return ans;
}

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:12:23: warning: array subscript -1 is below array bounds of 'int [1005][2]' [-Warray-bounds]
   12 |     if (memo[cur][prev][k]) return memo[cur][prev][k];
      |         ~~~~~~~~~~~~~~^

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 5720 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 3672 KB Output is correct
11 Correct 1 ms 4188 KB Output is correct
12 Correct 2 ms 5724 KB Output is correct
13 Correct 2 ms 5724 KB Output is correct
14 Correct 1 ms 2908 KB Output is correct
15 Correct 2 ms 5720 KB Output is correct

Subtask #5
0 / 23.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Runtime error 39 ms 10804 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -