# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
166982 |
2019-12-05T06:47:55 Z |
davitmarg |
Friend (IOI14_friend) |
C++17 |
|
14 ms |
504 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] += dp[to][1];
}
}
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 (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
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += a[i];
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], sum - dp[0][1]);
}
}
return ans;
}
#ifdef death
int main()
{
return 0;
}
#endif
/*
7
5 6 7 1 2 3 4
7
5 6 7 1 2 10 4
7
2 3 4 9 6 7 1
1 2 3 4 9 6 7
*/
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++)
~~^~~~~~~~~~~~~
# |
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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
424 KB |
Output is correct |
5 |
Correct |
3 ms |
424 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
3 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 |
376 KB |
Output is correct |
2 |
Correct |
3 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 |
14 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 |
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 |
504 KB |
Output is correct |
6 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
6 |
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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |