#include<bits/stdc++.h>
// Define
const int N = 100005;
using namespace std;
int da[N], nu[N];
struct sonsh{
int nod, pt;
};
vector<sonsh> sons[N];
int cost[N];
// Find out answer
void dfs(int nod){
da[nod] = cost[nod];
nu[nod] = 0;
for(int i = sons[nod].size() - 1; i>=0; i--){
int sn = sons[nod][i].nod;
dfs(sn);
int dah = 0, nuh = 0;
if(sons[nod][i].pt == 0){ // IAmYourFriend
dah = da[nod] + nu[sn];
nuh = max(nu[nod] + nu[sn], nu[nod] + da[sn]);
}
else if(sons[nod][i].pt == 1){ // MyFriendsAreYourFriends
dah = max({nu[nod] + da[sn], da[nod] + nu[sn], da[nod] + da[sn]});
nuh = nu[nod] + nu[sn];
}
else if(sons[nod][i].pt == 2){ // We AreYourFriends
dah = max({nu[nod] + da[sn], da[nod] + nu[sn]});
nuh = nu[nod] + nu[sn];
}
da[nod] = dah;
nu[nod] = nuh;
}
}
int findSample(int n,int confidence[],int host[],int protocol[]){
for(int i = 0; i < n; i++)
cost[i] = confidence[i];
for(int i = 1; i < n; i++){
sons[host[i]].push_back({i, protocol[i]});
}
dfs(0);
return max(da[0], nu[0]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2564 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2768 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2688 KB |
Output is correct |
9 |
Correct |
2 ms |
2648 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
2684 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2764 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2764 KB |
Output is correct |
10 |
Correct |
2 ms |
2764 KB |
Output is correct |
11 |
Correct |
2 ms |
2656 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2660 KB |
Output is correct |
14 |
Correct |
2 ms |
2660 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
2 ms |
2652 KB |
Output is correct |
18 |
Correct |
2 ms |
2652 KB |
Output is correct |
19 |
Correct |
2 ms |
2640 KB |
Output is correct |
20 |
Correct |
2 ms |
2636 KB |
Output is correct |
21 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2660 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
46 ms |
8064 KB |
Output is correct |
13 |
Correct |
23 ms |
5396 KB |
Output is correct |
14 |
Correct |
42 ms |
7496 KB |
Output is correct |
15 |
Correct |
41 ms |
7528 KB |
Output is correct |