# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
517022 |
2022-01-22T11:30:44 Z |
AdamGS |
Friend (IOI14_friend) |
C++17 |
|
43 ms |
8004 KB |
#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<pair<int,int>>V[LIM];
int T[LIM], dp[LIM][2];
void DFS(int x) {
dp[x][1]=T[x];
for(auto i : V[x]) {
DFS(i.st);
if(i.nd==0) dp[x][0]+=max(dp[i.st][0], dp[i.st][1]);
else dp[x][0]+=dp[i.st][0];
if(i.nd==1) dp[x][1]+=max(dp[i.st][0], dp[i.st][1]);
else dp[x][1]+=dp[i.st][0];
}
int suf[V[x].size()+1];
suf[V[x].size()]=0;
for(int i=V[x].size()-1; i>=0; --i) {
suf[i]=suf[i+1];
if(V[x][i].nd==0) suf[i]+=max(dp[V[x][i].st][0], dp[V[x][i].st][1]);
else suf[i]+=dp[V[x][i].st][0];
}
int akt=0;
rep(i, V[x].size()) {
if(V[x][i].nd==1) {
akt+=max(dp[V[x][i].st][0], dp[V[x][i].st][1]);
} else {
dp[x][1]=max(dp[x][1], akt+max(dp[V[x][i].st][0], dp[V[x][i].st][1])+suf[i+1]);
akt+=dp[V[x][i].st][0];
}
}
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
rep(i, n) T[i]=confidence[i];
for(int i=1; i<n; ++i) V[host[i]].pb({i, protocol[i]});
DFS(0);
return max(dp[0][0], dp[0][1]);
}
Compilation message
friend.cpp: In function 'void DFS(int)':
friend.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
friend.cpp:31:2: note: in expansion of macro 'rep'
31 | rep(i, V[x].size()) {
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2656 KB |
Output is correct |
4 |
Correct |
1 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
1 ms |
2636 KB |
Output is correct |
7 |
Correct |
1 ms |
2636 KB |
Output is correct |
8 |
Correct |
1 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2660 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 |
2656 KB |
Output is correct |
14 |
Correct |
1 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2656 KB |
Output is correct |
16 |
Correct |
1 ms |
2636 KB |
Output is correct |
17 |
Correct |
2 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 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 |
3 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2660 KB |
Output is correct |
7 |
Correct |
2 ms |
2660 KB |
Output is correct |
8 |
Correct |
3 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2656 KB |
Output is correct |
2 |
Correct |
2 ms |
2664 KB |
Output is correct |
3 |
Correct |
1 ms |
2656 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 |
2676 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2756 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2764 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
1 ms |
2636 KB |
Output is correct |
4 |
Correct |
1 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 |
2656 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
1 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2660 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 |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2764 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
1 ms |
2636 KB |
Output is correct |
8 |
Correct |
1 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2764 KB |
Output is correct |
10 |
Correct |
2 ms |
2728 KB |
Output is correct |
11 |
Correct |
2 ms |
2596 KB |
Output is correct |
12 |
Correct |
3 ms |
2656 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2664 KB |
Output is correct |
15 |
Correct |
2 ms |
2660 KB |
Output is correct |
16 |
Correct |
1 ms |
2636 KB |
Output is correct |
17 |
Correct |
2 ms |
2636 KB |
Output is correct |
18 |
Correct |
2 ms |
2636 KB |
Output is correct |
19 |
Correct |
1 ms |
2636 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 |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
1 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
1 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 |
1 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
1 ms |
2636 KB |
Output is correct |
12 |
Correct |
39 ms |
8004 KB |
Output is correct |
13 |
Correct |
24 ms |
5444 KB |
Output is correct |
14 |
Correct |
43 ms |
7384 KB |
Output is correct |
15 |
Correct |
34 ms |
7492 KB |
Output is correct |