| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 379701 |
2021-03-19T03:56:09 Z |
jamielim |
Chase (CEOI17_chase) |
C++14 |
|
504 ms |
169512 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int n,v;
ll arr[100005];
vector<int> adj[100005];
ll sum[100005];
ll dp[2][105][100005];
ll ans=0;
inline ll mx(ll x,ll y){return (x>y?x:y);}
void dfs(int x,int p){
for(int i:adj[x]){
if(i==p)continue;
dfs(i,x);
}
for(int j=0;j<=v;j++){
dp[0][j][x]=dp[1][j][x]=0;
if(j!=0){
for(int i:adj[x]){
if(i==p)continue;
dp[0][j][x]=mx(dp[0][j][x],dp[0][j-1][i]-arr[i]);
dp[1][j][x]=mx(dp[1][j][x],dp[1][j-1][i]);
}
dp[0][j][x]+=sum[x];
dp[1][j][x]+=sum[x]-arr[p];
}
for(int i:adj[x]){
if(i==p)continue;
dp[0][j][x]=mx(dp[0][j][x],dp[0][j][i]);
dp[1][j][x]=mx(dp[1][j][x],dp[1][j][i]);
}
}
}
void dfs2(int x,int p){
for(int j=0;j<v;j++){
ii idk[2][2];idk[0][0]=idk[0][1]=mp(0,-1);idk[1][0]=idk[1][1]=mp(0,-2);
for(int i:adj[x]){
if(i==p)continue;
if(dp[0][j][i]+sum[x]-arr[i]>idk[0][1].fi)idk[0][1]=mp(dp[0][j][i]+sum[x]-arr[i],i);
if(idk[0][1].fi>idk[0][0].fi)swap(idk[0][1],idk[0][0]);
if(dp[1][v-j-1][i]>idk[1][1].fi)idk[1][1]=mp(dp[1][v-j-1][i],i);
if(idk[1][1].fi>idk[1][0].fi)swap(idk[1][1],idk[1][0]);
}
if(idk[0][0].se!=idk[1][0].se)ans=mx(ans,idk[0][0].fi+idk[1][0].fi);
else ans=mx(ans,mx(idk[0][0].fi+idk[1][1].fi,idk[0][1].fi+idk[1][0].fi));
//printf("%lld %d %d\n",ans,j,x);
}
for(int j=0;j<=v;j++){
ii idk[2][2];idk[0][0]=idk[0][1]=mp(0,-1);idk[1][0]=idk[1][1]=mp(0,-2);
for(int i:adj[x]){
if(i==p)continue;
if(dp[0][j][i]>idk[0][1].fi)idk[0][1]=mp(dp[0][j][i],i);
if(idk[0][1].fi>idk[0][0].fi)swap(idk[0][1],idk[0][0]);
if(dp[1][v-j][i]>idk[1][1].fi)idk[1][1]=mp(dp[1][v-j][i],i);
if(idk[1][1].fi>idk[1][0].fi)swap(idk[1][1],idk[1][0]);
}
if(idk[0][0].se!=idk[1][0].se)ans=mx(ans,idk[0][0].fi+idk[1][0].fi);
else ans=mx(ans,mx(idk[0][0].fi+idk[1][1].fi,idk[0][1].fi+idk[1][0].fi));
//printf("%lld %d %d\n",ans,j,x);
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
int a,b;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);a--;b--;
adj[a].pb(b);adj[b].pb(a);
}
for(int i=0;i<n;i++)for(int j:adj[i])sum[i]+=arr[j];
dfs(0,-1);
dfs2(0,-1);
printf("%lld",ans);
}
/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/
Compilation message
chase.cpp: In function 'int main()':
chase.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d%d",&n,&v);
| ~~~~~^~~~~~~~~~~~~~
chase.cpp:84:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | scanf("%d%d",&a,&b);a--;b--;
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
504 ms |
169512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
