| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 50520 | 2018-06-11T10:18:16 Z | mirbek01 | Friend (IOI14_friend) | C++17 | 66 ms | 14320 KB |
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 2;
int n, g[N][N], dp[N], ar[N], b[N];
vector <int> G[N];
void dfs(int v, int pr){
int ch = 0;
for(int to : G[v]){
if(to == pr) continue;
dfs(to, v);
ch += dp[to];
if(pr != -1)
b[pr] += dp[to];
}
dp[v] = max(b[v] + ar[v], ch);
}
// Find out best sample
int findSample(int N,int confidence[],int host[],int protocol[]){
n = N;
int ans = 0;
if(n <= 10){
for(int i = 1; i < n; i ++){
if(protocol[i]){
for(int j = 0; j < n; j ++){
if(g[host[i]][j])
g[j][i] = g[i][j] = 1;
}
}
if(protocol[i] != 1){
g[i][host[i]] = g[host[i]][i] = 1;
}
}
for(int mask = 0; mask < (1 << n); mask ++){
vector <int> v;
int sum = 0;
for(int i = 0; i < n; i ++){
int bit = (1 << i) & mask;
if(bit){
sum += confidence[i];
v.push_back(i);
}
}
bool fl = 1;
for(int i = 0; i < v.size(); i ++){
for(int j = i + 1; j < v.size(); j ++){
if(g[v[i]][v[j]]){
fl = 0;
}
}
}
if(fl) ans = max(ans, sum);
}
} else {
if(protocol[n - 1] == 2){
for(int i = 0; i < n; i ++)
ans = max(ans, confidence[i]);
} else if(protocol[n - 1]){
for(int i = 0; i < n; i ++){
ans += confidence[i];
}
} else {
for(int i = 1; i < n; i ++){
G[host[i]].push_back(i);
G[i].push_back(host[i]);
}
for(int i = 0; i < n; i ++)
ar[i] = confidence[i];
dfs(0, -1);
ans = dp[0];
}
}
return ans;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 376 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 2 ms | 428 KB | Output is correct |
| 4 | Correct | 2 ms | 644 KB | Output is correct |
| 5 | Correct | 2 ms | 680 KB | Output is correct |
| 6 | Correct | 2 ms | 680 KB | Output is correct |
| 7 | Correct | 3 ms | 680 KB | Output is correct |
| 8 | Correct | 3 ms | 680 KB | Output is correct |
| 9 | Correct | 3 ms | 680 KB | Output is correct |
| 10 | Correct | 2 ms | 680 KB | Output is correct |
| 11 | Correct | 3 ms | 680 KB | Output is correct |
| 12 | Correct | 2 ms | 680 KB | Output is correct |
| 13 | Correct | 2 ms | 680 KB | Output is correct |
| 14 | Correct | 2 ms | 680 KB | Output is correct |
| 15 | Correct | 3 ms | 680 KB | Output is correct |
| 16 | Correct | 2 ms | 680 KB | Output is correct |
| 17 | Correct | 3 ms | 680 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 680 KB | Output is correct |
| 2 | Correct | 2 ms | 740 KB | Output is correct |
| 3 | Correct | 3 ms | 740 KB | Output is correct |
| 4 | Correct | 3 ms | 740 KB | Output is correct |
| 5 | Correct | 2 ms | 740 KB | Output is correct |
| 6 | Correct | 2 ms | 740 KB | Output is correct |
| 7 | Correct | 2 ms | 740 KB | Output is correct |
| 8 | Correct | 2 ms | 740 KB | Output is correct |
| 9 | Correct | 2 ms | 740 KB | Output is correct |
| 10 | Correct | 2 ms | 740 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 740 KB | Output is correct |
| 2 | Correct | 2 ms | 740 KB | Output is correct |
| 3 | Correct | 2 ms | 740 KB | Output is correct |
| 4 | Correct | 3 ms | 740 KB | Output is correct |
| 5 | Correct | 3 ms | 740 KB | Output is correct |
| 6 | Correct | 2 ms | 740 KB | Output is correct |
| 7 | Correct | 2 ms | 740 KB | Output is correct |
| 8 | Correct | 2 ms | 740 KB | Output is correct |
| 9 | Correct | 2 ms | 740 KB | Output is correct |
| 10 | Correct | 4 ms | 740 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 740 KB | Output is correct |
| 2 | Correct | 2 ms | 740 KB | Output is correct |
| 3 | Correct | 2 ms | 740 KB | Output is correct |
| 4 | Correct | 2 ms | 740 KB | Output is correct |
| 5 | Correct | 3 ms | 764 KB | Output is correct |
| 6 | Correct | 2 ms | 764 KB | Output is correct |
| 7 | Correct | 3 ms | 764 KB | Output is correct |
| 8 | Correct | 3 ms | 764 KB | Output is correct |
| 9 | Correct | 2 ms | 764 KB | Output is correct |
| 10 | Correct | 2 ms | 764 KB | Output is correct |
| 11 | Correct | 2 ms | 764 KB | Output is correct |
| 12 | Correct | 2 ms | 764 KB | Output is correct |
| 13 | Correct | 3 ms | 764 KB | Output is correct |
| 14 | Correct | 2 ms | 764 KB | Output is correct |
| 15 | Correct | 2 ms | 764 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 764 KB | Output is correct |
| 2 | Correct | 2 ms | 764 KB | Output is correct |
| 3 | Correct | 2 ms | 764 KB | Output is correct |
| 4 | Correct | 2 ms | 764 KB | Output is correct |
| 5 | Correct | 2 ms | 764 KB | Output is correct |
| 6 | Correct | 2 ms | 764 KB | Output is correct |
| 7 | Correct | 2 ms | 764 KB | Output is correct |
| 8 | Correct | 2 ms | 764 KB | Output is correct |
| 9 | Correct | 2 ms | 764 KB | Output is correct |
| 10 | Correct | 2 ms | 764 KB | Output is correct |
| 11 | Incorrect | 2 ms | 764 KB | Output isn't correct |
| 12 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 764 KB | Output is correct |
| 2 | Correct | 2 ms | 764 KB | Output is correct |
| 3 | Correct | 2 ms | 764 KB | Output is correct |
| 4 | Correct | 2 ms | 764 KB | Output is correct |
| 5 | Correct | 2 ms | 764 KB | Output is correct |
| 6 | Correct | 3 ms | 764 KB | Output is correct |
| 7 | Correct | 2 ms | 764 KB | Output is correct |
| 8 | Correct | 2 ms | 764 KB | Output is correct |
| 9 | Correct | 2 ms | 764 KB | Output is correct |
| 10 | Correct | 2 ms | 764 KB | Output is correct |
| 11 | Correct | 2 ms | 764 KB | Output is correct |
| 12 | Runtime error | 66 ms | 14320 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Halted | 0 ms | 0 KB | - |