# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
166995 |
2019-12-05T07:27:54 Z |
davitmarg |
Friend (IOI14_friend) |
C++17 |
|
39 ms |
2808 KB |
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000009ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
#ifndef death
#include "friend.h"
#endif
const int N = 1003;
int dp[N][2], a[N];
vector<int> g[N];
void dfs(int v, int p)
{
dp[v][1] = a[v];
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p)
continue;
dfs(to, v);
dp[v][1] += dp[to][0];
dp[v][0] += max(dp[to][1], dp[to][0]);
}
}
int findSample(int n, int confidence[], int host[], int protocol[])
{
int ans = 0;
set<int> type;
for (int i = 1; i < n; i++)
type.insert(protocol[i]);
for (int i = 0; i < n; i++)
a[i] = confidence[i];
if (n <= 10)
{
for (int i = 1; i < n; i++)
{
if (protocol[i] != 0)
for (int j = 0; j < g[host[i]].size(); j++)
{
g[g[host[i]][j]].PB(i);
g[i].PB(g[host[i]][j]);
}
if (protocol[i] != 1)
{
g[host[i]].PB(i);
g[i].PB(host[i]);
}
}
for (int mask = 0; mask < (1 << n); mask++)
{
bool norm = 1;
int sum = 0;
for (int i = 0; i < n; i++)
{
if (((1 << i) & mask) == 0)
continue;
sum += a[i];
for (int j = 0; j < g[i].size(); j++)
{
int to = g[i][j];
if (((1 << to) & mask) != 0)
{
norm = 0;
break;
}
}
}
if (norm)
ans = max(ans, sum);
}
return ans;
}
if (type.size() == 1)
{
if ((*type.begin()) == 2)
{
sort(confidence, confidence + n);
ans = confidence[n - 1];
}
else if ((*type.begin()) == 1)
{
for (int i = 0; i < n; i++)
ans += a[i];
}
else
{
for (int i = 1; i < n; i++)
{
g[host[i]].PB(i);
g[i].PB(host[i]);
}
dfs(0, -1);
ans = max(dp[0][1], dp[0][0]);
}
}
return ans;
}
#ifdef death
int main()
{
int conf[N], prot[N], host[N];
int n, i;
// Number of people
assert(scanf("%d", &n) == 1);
// Confidence
for (i = 0; i < n; i++)
assert(scanf("%d", &conf[i]) == 1);
// Host and Protocol
for (i = 1; i < n; i++)
assert(scanf("%d %d", &host[i], &prot[i]) == 2);
// Answer
printf("%d\n", findSample(n, conf, host, prot));
return 0;
}
#endif
/*
*/
Compilation message
friend.cpp: In function 'void dfs(int, int)':
friend.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:63:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[host[i]].size(); j++)
~~^~~~~~~~~~~~~~~~~~~
friend.cpp:83:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j++)
~~^~~~~~~~~~~~~
# |
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 |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
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 |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
372 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
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 |
6 ms |
404 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
508 KB |
Output is correct |
10 |
Correct |
3 ms |
504 KB |
Output is correct |
11 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
404 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Incorrect |
39 ms |
2808 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |