Submission #66579

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66579	2018-08-11T16:27:15 Z	aquablitz11	Friend (IOI14_friend)	C++14	46 / 100	44 ms	4832 KB

friend

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

const int N = 1010;

int n, *conf;
bool act[N];
vector<int> G[N];

int solve(int u)
{
    if (u == n)
        return 0;
    bool can = true;
    for (auto v : G[u]) if (act[v])
        can = false;
    int ans = 0;
    if (can) {
        act[u] = true;
        ans = max(ans, conf[u]+solve(u+1));
    }
    act[u] = false;
    ans = max(ans, solve(u+1));
    return ans;
}

int dp[N][2];
void dfs(int u, int p)
{
    dp[u][1] = conf[u];
    for (auto v : G[u]) if (v != p) {
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int findSample(int n, int confidence[], int host[], int protocol[])
{
    if (n > 100000) return -1;
    ::n = n;
    conf = confidence;
    for (int i = 1; i < n; ++i) {
        if (protocol[i] != 0) {
            for (auto v : G[host[i]]) {
                G[i].push_back(v);
                G[v].push_back(i);
            }
        }
        if (protocol[i] != 1) {
            G[i].push_back(host[i]);
            G[host[i]].push_back(i);
        }
    }
    if (n <= 10)
        return solve(0);
    if (protocol[1] == 1) {
        int sum = 0;
        for (int i = 0; i < n; ++i)
            sum += conf[i];
        return sum;
    }
    if (protocol[1] == 2) {
        int mx = 0;
        for (int i = 0; i < n; ++i)
            mx = max(mx, conf[i]);
        return mx;
    }
    dfs(0, 0);
    return max(dp[0][0], dp[0][1]);
}

Subtask #1

11.0 / 11.0

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

Subtask #2

8.0 / 8.0

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

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1516 KB	Output is correct
2	Correct	17 ms	4448 KB	Output is correct
3	Correct	2 ms	4448 KB	Output is correct
4	Correct	10 ms	4448 KB	Output is correct
5	Correct	12 ms	4508 KB	Output is correct
6	Correct	2 ms	4508 KB	Output is correct
7	Correct	4 ms	4508 KB	Output is correct
8	Correct	4 ms	4508 KB	Output is correct
9	Correct	2 ms	4508 KB	Output is correct
10	Correct	13 ms	4832 KB	Output is correct

Subtask #4

19.0 / 19.0

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

Subtask #5

0 / 23.0

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

Subtask #6

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4832 KB	Output is correct
2	Correct	2 ms	4832 KB	Output is correct
3	Correct	2 ms	4832 KB	Output is correct
4	Correct	2 ms	4832 KB	Output is correct
5	Correct	3 ms	4832 KB	Output is correct
6	Correct	3 ms	4832 KB	Output is correct
7	Correct	2 ms	4832 KB	Output is correct
8	Correct	2 ms	4832 KB	Output is correct
9	Correct	3 ms	4832 KB	Output is correct
10	Correct	2 ms	4832 KB	Output is correct
11	Correct	2 ms	4832 KB	Output is correct
12	Runtime error	44 ms	4832 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Halted	0 ms	0 KB	-