# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
166547 |
2019-12-02T18:15:51 Z |
faremy |
Friend (IOI14_friend) |
C++14 |
|
56 ms |
8440 KB |
#include "friend.h"
#include <algorithm>
#include <vector>
struct Edge
{
Edge(int e, bool d, bool b) : end(e), isDirect(d), isBlocking(b) {}
int end;
bool isDirect, isBlocking;
};
const int MAXN = 1e5;
std::vector<Edge> network[MAXN];
int value[MAXN];
int bestSample[MAXN][2][2];
void sample(int node)
{
int sumBlocking = 0;
for (Edge &edge : network[node])
{
sample(edge.end);
int weight = std::max(std::max(bestSample[edge.end][0][0], bestSample[edge.end][0][1]), std::max(bestSample[edge.end][1][0], bestSample[edge.end][1][1]));
if (edge.isBlocking)
{
bestSample[node][0][0] += bestSample[edge.end][0][0];
bestSample[node][1][0] += bestSample[edge.end][0][0];
if (edge.isDirect)
{
bestSample[node][1][1] += bestSample[edge.end][0][0];
bestSample[node][0][1] = std::max(bestSample[node][0][1] + bestSample[edge.end][0][0], sumBlocking + weight);
sumBlocking += bestSample[edge.end][0][0];
}
else
{
bestSample[node][1][1] += weight;
sumBlocking += weight;
bestSample[node][0][1] = std::max(bestSample[node][0][1] + bestSample[edge.end][0][0], sumBlocking);
}
}
else
{
bestSample[node][0][0] += weight;
bestSample[node][1][0] += bestSample[edge.end][0][0];
bestSample[node][1][1] += bestSample[edge.end][0][0];
sumBlocking += bestSample[edge.end][0][0];
bestSample[node][0][1] += weight;
}
}
}
int findSample(int n, int confidence[], int host[], int protocol[])
{
for (int iNode = 0; iNode < n; iNode++)
bestSample[iNode][1][0] = bestSample[iNode][1][1] = confidence[iNode];
for (int iEdge = 1; iEdge < n; iEdge++)
network[host[iEdge]].emplace_back(iEdge, (protocol[iEdge] % 2 == 0), (protocol[iEdge] > 0));
sample(0);
return std::max(std::max(bestSample[0][0][0], bestSample[0][0][1]), std::max(bestSample[0][1][0], bestSample[0][1][1]));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2552 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2684 KB |
Output is correct |
11 |
Correct |
4 ms |
2744 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
13 |
Correct |
4 ms |
2680 KB |
Output is correct |
14 |
Correct |
4 ms |
2680 KB |
Output is correct |
15 |
Correct |
4 ms |
2680 KB |
Output is correct |
16 |
Correct |
4 ms |
2680 KB |
Output is correct |
17 |
Correct |
4 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2728 KB |
Output is correct |
3 |
Correct |
4 ms |
2652 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
5 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2808 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2680 KB |
Output is correct |
11 |
Correct |
4 ms |
2680 KB |
Output is correct |
12 |
Correct |
4 ms |
2808 KB |
Output is correct |
13 |
Correct |
4 ms |
2680 KB |
Output is correct |
14 |
Correct |
4 ms |
2680 KB |
Output is correct |
15 |
Correct |
5 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
13 |
Correct |
4 ms |
2680 KB |
Output is correct |
14 |
Correct |
4 ms |
2680 KB |
Output is correct |
15 |
Correct |
4 ms |
2680 KB |
Output is correct |
16 |
Correct |
4 ms |
2680 KB |
Output is correct |
17 |
Correct |
4 ms |
2680 KB |
Output is correct |
18 |
Correct |
4 ms |
2680 KB |
Output is correct |
19 |
Correct |
4 ms |
2680 KB |
Output is correct |
20 |
Correct |
4 ms |
2680 KB |
Output is correct |
21 |
Correct |
4 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2680 KB |
Output is correct |
11 |
Correct |
4 ms |
2680 KB |
Output is correct |
12 |
Correct |
56 ms |
8440 KB |
Output is correct |
13 |
Correct |
30 ms |
5624 KB |
Output is correct |
14 |
Correct |
52 ms |
7840 KB |
Output is correct |
15 |
Correct |
50 ms |
7928 KB |
Output is correct |