# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
374548 |
2021-03-07T12:33:17 Z |
idk321 |
Friend (IOI14_friend) |
C++11 |
|
30 ms |
1516 KB |
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
vector<int> adj[N];
// Find out best sample
int dp[N][2];
int* conf;
int n;
bool open[N];
int dfs(int node, int par)
{
dp[node][0] = 0;
dp[node][1] = conf[node];
for (int next : adj[node])
{
if (next == par) continue;
dfs(next, node);
dp[node][0] += max(dp[next][0], dp[next][1]);
dp[node][1] += dp[next][0];
}
return max(dp[node][0], dp[node][1]);
}
bool legal(int node)
{
for (int next : adj[node])
{
if (open[next]) return false;
}
return true;
}
int go(int i, int sum)
{
if (i == n)
{
bool ok = true;
for (int j = 0; j< n; j++) if (open[j])ok = ok && legal(j);
if (ok) return sum;
return 0;
}
int best = 0;
best = max(best, go(i + 1, sum));
open[i] = true;
best = max(best, go(i + 1, sum + conf[i]));
open[i] = false;
return best;
}
int findSample(int n1,int conf1[],int host[],int pro[]){
n = n1;
conf = conf1;
int ans=10;
int freq[3] = {};
for (int i = 1; i < n; i++) freq[pro[i]]++;
if (freq[0] == 0 && freq[2] == 0)
{
int sum = 0;
for (int i = 0; i < n; i++) sum += conf[i];
return sum;
} else if (freq[0] == 0 && freq[1] == 0)
{
int res = 0;
for (int i = 0; i < n; i++) res = max(res, conf[i]);
return res;
} else if (freq[1] == 0 && freq[2] == 0)
{
for (int i = 1; i < n; i++)
{
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
}
return dfs(0, -1);
} else if (n <= 10)
{
for (int i = 1; i < n; i++)
{
if (pro[i] == 0)
{
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
} else if (pro[i] == 1)
{
for (int j : adj[host[i]])
{
adj[i].push_back(j);
adj[j].push_back(i);
}
} else
{
for (int j : adj[host[i]])
{
adj[i].push_back(j);
adj[j].push_back(i);
}
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
}
}
return go(0, 0);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Incorrect |
30 ms |
1516 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |