oj.uz

Submission #614106

# Submission time Handle Problem Language Result Execution time Memory
614106 2022-07-30T18:51:14 Z leaked Chase (CEOI17_chase) C++17
50 / 100
 840 ms 337828 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
const ll inf=1e18;
const int N=1e5+1;
//#define int long lon

int a[N],cnt,n;
vec<int> g[N];
ll sm[N];

ll ans=0;

ll dpu[N][102][2];
ll dpd[N][102][2];
/// i'ma on and how many

//
//void dfs(int v,int p){
//    for(auto &z : g[v]){
//        if(z==p) continue;
//        for(int t=0;t<2;t++){
//            for(int j=0;j<=cnt;j++){
//                /// skip
//                umax(dp[z][j][1],dp[v][j][t]);
//                if(j+1<=cnt){
//                    /// add z
//                    ll cost=dp[v][j][t]+sm[z]-a[v]-a[z];
//                    umax(dp[z][j+1][0],cost);
//                }
//            }
//        }
//        dfs(z,v);
//    }
//}


void dfs1(int v,int p){

    for(int j=1;j<=cnt;j++){
        for(int t=0;t<2;t++){
            dpd[v][j][t]=(t==0?sm[v]-a[v]:0);
            dpu[v][j][t]=(t==0?sm[v]-a[v]:0);
        }
    }

    dpu[v][0][1]=0;dpd[v][0][1]=0;

    for(auto &z : g[v]){
        if(z==p) continue;
        dfs1(z,v);
    }

//    cout<<"REC " <<v<<endl;
    for(auto &z : g[v]){
        if(z==p) continue;


        vec<vec<ll>> ndpu(cnt+1,vec<ll>(2,-inf));



        for(int t=0;t<2;t++){
            for(int j=0;j<=cnt;j++){
                /// 0, v v will be
                if(j+1<=cnt){
                    umax(ndpu[j+1][t],ndpu[j][t]);
                    umax(ndpu[j+1][0],dpu[z][j][t]-a[v]-a[z]+sm[v]);
                }
                /// 1
                umax(ndpu[j][1],dpu[z][j][t]);
            }
        }

        for(int j=1;j<=cnt-1;j++){
            int k=cnt-j;
            umax(ans,dpd[v][j][0]+ndpu[k+1][0]-sm[v]+a[v]);
        }

//        cout<<"ZI "<<z<<endl;
        for(int j=1;j<=cnt;j++){
            umax(ans,ndpu[j][1]+dpd[v][cnt-j][1]);
////            cout<<ndpu[j][1]+dpd[v][cnt-j][1]<<' '<<dpd[v][cnt-j][1]<<' '<<ndpu[j][1]<<endl;
        }

        for(int t=0;t<2;t++){
            for(int j=0;j<=cnt;j++){
                /// 0, v v will be
                int valt=-(t==0? a[v] : 0);
                if(j+1<=cnt){
                    umax(dpd[v][j+1][t],dpd[v][j][t]);

                    umax(dpd[v][j+1][0],dpd[z][j][t]-a[v]+sm[v]+valt);
                }
                /// 1
                umax(dpd[v][j][1],dpd[z][j][t]+valt);
            }
        }



        for(int j=0;j<=cnt;j++){
            for(int t=0;t<2;t++)
                umax(dpu[v][j][t],ndpu[j][t]);
        }

    }
//    cout<<"CLOSE "<<v<<endl;
    umax(ans,dpd[v][cnt][1]);
    umax(ans,dpu[v][cnt][1]);
    umax(ans,dpu[v][cnt][0]);
    umax(ans,dpd[v][cnt][0]);

//    cout<<"V" <<v<<' '<<ans<<endl;

}

signed main(){
    fast_ioi;
    cin>>n>>cnt;

    for(int i=0;i<n;i++) cin>>a[i];

    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }

    for(int i=0;i<n;i++){
        sm[i]+=a[i];
        for(auto &z : g[i])
            sm[i]+=a[z];
    }
//    cout<<sm[5]<<endl;
    auto upd=[&](){
        for(int v=0;v<n;v++){
            for(int h=0;h<=cnt;h++){
                for(int t=0;t<2;t++)
                    dpd[v][h][t]=dpu[v][h][t]=-inf;
            }
        }
    };
    upd();

    dfs1(0,0);


    cout<<ans;
    return 0;
}
/*
10 3
10 1 1 1 1 10 1 10 1 10
1 2
2 3
3 4
4 5
5 6
3 7
7 8
9 4
9 10

*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 9 ms 5988 KB Output is correct
8 Correct 4 ms 5996 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Incorrect 10 ms 5964 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 337828 KB Output is correct
2 Correct 762 ms 337772 KB Output is correct
3 Correct 710 ms 328784 KB Output is correct
4 Correct 183 ms 328472 KB Output is correct
5 Correct 734 ms 328672 KB Output is correct
6 Correct 754 ms 328624 KB Output is correct
7 Correct 749 ms 328548 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 9 ms 5988 KB Output is correct
8 Correct 4 ms 5996 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Incorrect 10 ms 5964 KB Output isn't correct
11 Halted 0 ms 0 KB -