| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 921622 |
2024-02-04T08:19:24 Z |
PM1 |
Chase (CEOI17_chase) |
C++17 |
|
4000 ms |
73160 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mxn=1e5+5,mxv=102;
ll n,vv,p[mxn],par[mxn],sz[mxn];
ll a[mxn],dp[3][mxn][mxv],ans,mx[3][mxv];
vector<ll>v[mxn];
void fds(ll z,ll root ,ll poot){
for(ll i=1;i<=vv;i++){
dp[0][z][i]=max({dp[0][z][i-1],dp[0][par[z]][i-1]+a[z]-p[par[z]],dp[0][par[z]][i]});
ans=max(ans,dp[0][z][i]+mx[1][vv-i]-p[root]);
ans=max(ans,dp[0][z][i]+mx[2][vv-i]);
}
for(auto j:v[z]){
if(par[z]!=j){
fds(j,root,poot);
for(ll i=1;i<=vv;i++){
dp[1][z][i]=max({dp[1][z][i-1],dp[1][j][i-1]+a[z]-p[j],dp[2][j][i-1]+a[z]-p[j]});
dp[2][z][i]=max({dp[2][z][i-1],dp[2][j][i],dp[1][j][i]});
}
}
}
for(ll i=1;i<=vv;i++){
dp[1][z][i]=max(dp[1][z][i-1],a[z]);
}
if(z==poot){
for(ll i=1;i<=vv;i++){
ans=max(ans,dp[1][z][i]+mx[0][vv-i]-p[poot]);
ans=max(ans,dp[2][z][i]+mx[0][vv-i]);
}
}
}
void up(ll z){
for(ll i=1;i<=vv;i++){
dp[0][z][i]=max({dp[0][z][i-1],dp[0][par[z]][i-1]+a[z]-p[par[z]],dp[0][par[z]][i]});
mx[0][i]=max(mx[0][i],dp[0][z][i]);
}
for(auto j:v[z]){
if(par[z]!=j){
up(j);
for(ll i=1;i<=vv;i++){
dp[1][z][i]=max({dp[1][z][i-1],dp[1][j][i-1]+a[z]-p[j],dp[2][j][i-1]+a[z]-p[j]});
dp[2][z][i]=max({dp[2][z][i-1],dp[2][j][i],dp[1][j][i]});
mx[1][i]=max(mx[1][i],dp[1][z][i]);
mx[2][i]=max(mx[2][i],dp[2][z][i]);
}
}
}
for(ll i=1;i<=vv;i++){
dp[1][z][i]=max(dp[1][z][i-1],a[z]);
mx[1][i]=max(mx[1][i],dp[1][z][i]);
mx[2][i]=max(mx[2][i],dp[2][z][i]);
}
}
void dfs(ll z){
sz[z]=1;
ll big=0;
for(auto i:v[z]){
if(par[z]!=i){
par[i]=z;
dfs(i);
sz[z]+=sz[i];
if(sz[big]<sz[i])big=i;
}
}
for(ll i=1;i<=vv;i++)
dp[0][z][i]=a[i];
if(big!=0){
up(big);
for(ll i=1;i<=vv;i++){
dp[1][z][i]=max({dp[1][z][i-1],dp[1][big][i-1]+a[z]-p[big],dp[2][big][i-1]+a[z]-p[big]});
dp[2][z][i]=max({dp[2][z][i-1],dp[2][big][i],dp[1][big][i]});
ans=max({ans,dp[1][z][i],dp[2][z][i]});
}
}
for(auto j:v[z]){
if(par[z]!=j && j!=big){
fds(j,z,j);
up(j);
for(ll i=1;i<=vv;i++){
dp[1][z][i]=max({dp[1][z][i-1],dp[1][j][i-1]+a[z]-p[j],dp[2][j][i-1]+a[z]-p[j]});
dp[2][z][i]=max({dp[2][z][i-1],dp[2][j][i],dp[1][j][i]});
ans=max({ans,dp[1][z][i],dp[2][z][i]});
}
}
}
for(int i=1;i<=vv;i++){
for(int j=0;j<3;j++)
ans=max(ans,mx[j][i]);
}
//cout<<z<<" "<<ans<<endl;
memset(mx,0,sizeof mx);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>vv;
for(ll i=1;i<=n;i++)
cin>>p[i];
for(ll i=1;i<n;i++){
ll x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
a[x]+=p[y];
a[y]+=p[x];
}
//cout<<endl;
dfs(1);
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4041 ms |
73160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
