| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 987709 |
2024-05-23T11:50:25 Z |
ErJ |
Chase (CEOI17_chase) |
C++17 |
|
4000 ms |
350532 KB |
#include<bits/stdc++.h>
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define inf 1000000000000000
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
struct node{
ll id;
vi dp1;
vi dp2;
ll sum = 0;
bool ready = false;
};
vector<node> nodes;
vi val;
struct edge{
ll from;
ll to;
vi dp;
bool ready = false;
ll anti = -1; //index anti edge v e.to FUJ
};
vector<vector<edge>> edges;
void readyEdge(edge &e){
ll sum = 0;
for(int i = 0; i < edges[e.to].size(); i++){
ll v = edges[e.to][i].to;
if(v != e.from){
sum += val[v];
if(!edges[e.to][i].ready){
readyEdge(edges[e.to][i]);
}
}
}
for(int i = 1; i < e.dp.size(); i++){
ll MAX1 = 0, MAX2 = 0;
for(int j = 0; j < edges[e.to].size(); j++){
ll v = edges[e.to][j].to;
if(v != e.from){
MAX1 = max(MAX1, edges[e.to][j].dp[i-1]);
MAX2 = max(MAX2, edges[e.to][j].dp[i]);
}
}
e.dp[i] = max(MAX1 + sum, MAX2);
}
e.ready = true;
}
void readyNode(int u){
rep(i, edges[u].size()){
ll v = edges[u][i].to;
nodes[u].sum += val[v];
rep(j, nodes[u].dp1.size()){
if(edges[u][i].dp[j] >= nodes[u].dp1[j]){
nodes[u].dp2[j] = nodes[u].dp1[j];
nodes[u].dp1[j] = edges[u][i].dp[j];
}else{
if(edges[u][i].dp[j] > nodes[u].dp2[j]){
nodes[u].dp2[j] = edges[u][i].dp[j];
}
}
}
}
nodes[u].ready = true;
}
void readyEdge2(edge &e){
ll sum = 0;
for(int i = 0; i < edges[e.to].size(); i++){
ll v = edges[e.to][i].to;
if(v != e.from){
sum += val[v];
if(!edges[e.to][i].ready){
readyEdge2(edges[e.to][i]);
}
}
}
if(!nodes[e.to].ready){
readyNode(e.to);
}
for(int i = 1; i < e.dp.size(); i++){
ll MAX1 = 0, MAX2 = 0;
/*for(int j = 0; j < edges[e.to].size(); j++){
ll v = edges[e.to][j].to;
if(v != e.from){
MAX1 = max(MAX1, edges[e.to][j].dp[i-1]);
MAX2 = max(MAX2, edges[e.to][j].dp[i]);
}
}*/
MAX1 = nodes[e.to].dp1[i- 1];
if(edges[e.to][e.anti].dp[i - 1] == nodes[e.to].dp1[i - 1]){
MAX1 = nodes[e.to].dp2[i - 1];
}
MAX2 = nodes[e.to].dp1[i];
if(edges[e.to][e.anti].dp[i] == nodes[e.to].dp1[i]){
MAX2 = nodes[e.to].dp2[i];
}
e.dp[i] = max(MAX1 + (nodes[e.to].sum - val[e.from]), MAX2);
}
e.ready = true;
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
ll n, v;
cin >> n >> v;
val.resize(n, 0);
rep(i,n){
cin >> val[i];
node no;
no.dp1.resize(v + 1, 0);
no.dp2.resize(v + 1, 0);
no.id = i;
no.ready = false;
no.sum = 0;
nodes.push_back(no);
}
edges.resize(n);
rep(i, n-1){
ll a, b;
cin >> a >> b;
a--; b--;
edge e, e1;
e.from = a;
e.to = b;
e.dp.resize(v + 1, 0);
e1.from = b;
e1.to = a;
e1.dp.resize(v + 1, 0);
e.anti = edges[b].size();
e1.anti = edges[a].size();
edges[a].push_back(e);
edges[b].push_back(e1);
}
if(v == 0){
cout << 0 << endl;
return 0;
}
rep(i, n){
rep(j, edges[i].size()){
if(!edges[i][j].ready){
if(i == 0){
readyEdge(edges[i][j]);
}else{
readyEdge2(edges[i][j]);
}
}
}
}
ll ans = 0;
rep(i, n){
ll sum = 0;
ll MAXV = 0, MAXV1 = 0;
rep(j, edges[i].size()){
sum += val[edges[i][j].to];
MAXV = max(MAXV, edges[i][j].dp[v]);
MAXV1 = max(MAXV1, edges[i][j].dp[v - 1]);
}
ans = max(ans, max(sum + MAXV1, MAXV));
}
cout << ans << endl;
}
Compilation message
chase.cpp: In function 'void readyEdge(edge&)':
chase.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < edges[e.to].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 1; i < e.dp.size(); i++){
| ~~^~~~~~~~~~~~~
chase.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int j = 0; j < edges[e.to].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp: In function 'void readyNode(int)':
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
61 | rep(i, edges[u].size()){
| ~~~~~~~~~~~~~~~~~~
chase.cpp:61:5: note: in expansion of macro 'rep'
61 | rep(i, edges[u].size()){
| ^~~
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
64 | rep(j, nodes[u].dp1.size()){
| ~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:64:9: note: in expansion of macro 'rep'
64 | rep(j, nodes[u].dp1.size()){
| ^~~
chase.cpp: In function 'void readyEdge2(edge&)':
chase.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0; i < edges[e.to].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 1; i < e.dp.size(); i++){
| ~~^~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
152 | rep(j, edges[i].size()){
| ~~~~~~~~~~~~~~~~~~
chase.cpp:152:9: note: in expansion of macro 'rep'
152 | rep(j, edges[i].size()){
| ^~~
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
166 | rep(j, edges[i].size()){
| ~~~~~~~~~~~~~~~~~~
chase.cpp:166:9: note: in expansion of macro 'rep'
166 | rep(j, edges[i].size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3932 KB |
Output is correct |
| 8 |
Correct |
3 ms |
860 KB |
Output is correct |
| 9 |
Correct |
3 ms |
860 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 12 |
Correct |
2 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
524 ms |
350400 KB |
Output is correct |
| 2 |
Correct |
558 ms |
350532 KB |
Output is correct |
| 3 |
Execution timed out |
4027 ms |
343796 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3932 KB |
Output is correct |
| 8 |
Correct |
3 ms |
860 KB |
Output is correct |
| 9 |
Correct |
3 ms |
860 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 12 |
Correct |
2 ms |
860 KB |
Output is correct |
| 13 |
Correct |
524 ms |
350400 KB |
Output is correct |
| 14 |
Correct |
558 ms |
350532 KB |
Output is correct |
| 15 |
Execution timed out |
4027 ms |
343796 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
