| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 161833 |
2019-11-04T15:06:28 Z |
Akashi |
Chase (CEOI17_chase) |
C++14 |
|
973 ms |
524292 KB |
#include <bits/stdc++.h>
using namespace std;
int n, V;
int val[100005];
bool viz[100005];
long long Sol, sum[100005];
long long down[100005][105][2], up[100005][105][2];
long long up2[100005][105][2], down2[100005][105][2];
long long up3[100005][105][2];
vector <int> v[100005];
void dfs(int nod = 1){
viz[nod] = 1;
for(auto fiu : v[nod]){
if(viz[fiu]) continue ;
dfs(fiu);
// if(nod == 7 && fiu == 6){
// bool ok = 0;
//
// }
for(int k = 1; k <= V ; ++k){
down[nod][k][0] = max(max(down[nod][k - 1][0], down[nod][k][0]), max(down[fiu][k][0], down[fiu][k][1] - val[nod]));
down[nod][k][1] = max(max(down[nod][k - 1][1], down[nod][k][1]), max(down[fiu][k - 1][0], down[fiu][k - 1][1] - val[nod]) + sum[nod]);
up[nod][k][0] = max(max(up[nod][k][0], up[nod][k - 1][0]), max(up[fiu][k][0], up[fiu][k][1]));
up[nod][k][1] = max(max(up[nod][k][1], up[nod][k - 1][1]), max(up[fiu][k - 1][0] - val[fiu], up[fiu][k - 1][1] - val[fiu]) + sum[nod]);
Sol = max(Sol, max(up[nod][k][0], up[nod][k][1]));
Sol = max(Sol, max(down[nod][k][0], down[nod][k][1]));
Sol = max(Sol,
max (
max(up[fiu][k][0] + down2[nod][V - k][0], up[fiu][k][1] + down2[nod][V - k][0]),
max(up[fiu][k][0] + down2[nod][V - k][1] - val[nod], up[fiu][k][1] + down2[nod][V - k][1] - val[nod])
)
);
Sol = max(Sol,
max (
max(down[fiu][k][0] + up2[nod][V - k][0], down[fiu][k][1] + up2[nod][V - k][0] - val[nod]),
max(down[fiu][k][0] + up2[nod][V - k][1], down[fiu][k][1] + up2[nod][V - k][1] - val[nod])
)
);
Sol = max(Sol,
max(
max(up[fiu][k - 1][0] + down2[nod][V - k][0] - val[fiu], up[fiu][k - 1][1] + down2[nod][V - k][0] - val[fiu]),
max(up[fiu][k - 1][0] + down2[nod][V - k][1] - val[fiu] - val[nod], up[fiu][k - 1][1] + down2[nod][V - k][1] - val[fiu] - val[nod])
) + sum[nod]
);
Sol = max(Sol,
max(
max(down[fiu][k - 1][0] + up3[nod][V - k][0], down[fiu][k - 1][1] + up3[nod][V - k][0] - val[nod]),
max(down[fiu][k - 1][0] + up3[nod][V - k][1] - val[nod], down[fiu][k - 1][1] + up2[nod][V - k][1] - val[nod])
) + sum[nod]
);
}
for(int k = 1; k <= V ; ++k){
down2[nod][k][0] = max(max(down2[nod][k - 1][0], down2[nod][k][0]), down[fiu][k][0]);
down2[nod][k][1] = max(max(down2[nod][k - 1][1], down2[nod][k][1]), down[fiu][k][1]);
up2[nod][k][0] = max(max(up2[nod][k][0], up2[nod][k - 1][0]), up[fiu][k][0]);
up2[nod][k][1] = max(max(up2[nod][k][1], up2[nod][k - 1][1]), up[fiu][k][1]);
up3[nod][k][0] = max(max(up3[nod][k][0], up3[nod][k - 1][0]), up[fiu][k][1] - val[fiu]);
up3[nod][k][1] = max(max(up3[nod][k][1], up3[nod][k - 1][1]), up[fiu][k][1] - val[fiu]);
}
}
bool ok = 0;
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d%d", &n, &V);
for(int i = 1; i <= n ; ++i)
scanf("%d", &val[i]);
int x, y;
for(int i = 2; i <= n ; ++i){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
sum[x] += val[y];
sum[y] += val[x];
}
dfs();
printf("%lld", Sol);
return 0;
}
Compilation message
chase.cpp: In function 'void dfs(int)':
chase.cpp:78:10: warning: unused variable 'ok' [-Wunused-variable]
bool ok = 0;
^~
chase.cpp: In function 'int main()':
chase.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &V);
~~~~~^~~~~~~~~~~~~~~~
chase.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &val[i]);
~~~~~^~~~~~~~~~~~~~~
chase.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
973 ms |
430824 KB |
Output is correct |
| 2 |
Correct |
956 ms |
430712 KB |
Output is correct |
| 3 |
Correct |
432 ms |
10420 KB |
Output is correct |
| 4 |
Runtime error |
808 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
