oj.uz

Submission #409513

# Submission time Handle Problem Language Result Execution time Memory
409513 2021-05-21T02:38:26 Z rrrr10000 Chase (CEOI17_chase) C++14
100 / 100
 1153 ms 516896 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

int main(){
    ll n,k;cin>>n>>k;
    vvi dp(n,vi(k+1)),dp2(n,vi(k+1));
    vi v(n);rep(i,n)cin>>v[i];
    vvi g(n);rep(i,n-1){ll a,b;cin>>a>>b;a--;b--;g[a].pb(b);g[b].pb(a);}
    function<void(ll,ll)> dfs=[&](ll i,ll p){
        ll ch=0;
        for(ll x:g[i])if(x!=p){
            dfs(x,i);
            rep(j,k+1)chmax(dp[i][j],dp[x][j]);
            ch+=v[x];
        }
        for(int j=k;j>0;j--)chmax(dp[i][j],dp[i][j-1]+ch);
    };dfs(0,-1);
    ll ans=0;
    function<void(ll,ll)> dfs2=[&](ll i,ll p){
        ll ch=0;for(ll x:g[i])ch+=v[x];
        rep(j,k+1){
            ll ma=dp2[i][j];
            for(ll x:g[i])if(x!=p)chmax(ma,dp[x][j]);
            chmax(ans,ma);
            if(j!=k)chmax(ans,ma+ch);
        }
        vvi l(g[i].size()+1,vi(k+1)),r(g[i].size()+1,vi(k+1));
        rep(t,k+1){
            rep(j,g[i].size()){
                if(g[i][j]==p)l[j+1][t]=max(l[j][t],dp2[i][t]);
                else l[j+1][t]=max(l[j][t],dp[g[i][j]][t]);
            }
            for(int j=g[i].size();j;j--){
                if(g[i][j-1]==p)r[j-1][t]=max(r[j][t],dp2[i][t]);
                else r[j-1][t]=max(r[j][t],dp[g[i][j-1]][t]);
            }
        }
        rep(j,g[i].size())if(g[i][j]!=p){
            rep(t,k+1)chmax(dp2[g[i][j]][t],max(l[j][t],r[j+1][t]));
            rep(t,k)chmax(dp2[g[i][j]][t+1],max(l[j][t],r[j+1][t])+ch-v[g[i][j]]);
            dfs2(g[i][j],i);
        }
    };dfs2(0,-1);
    out(ans);
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 10 ms 5420 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 8 ms 2100 KB Output is correct
11 Correct 4 ms 972 KB Output is correct
12 Correct 3 ms 588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 513948 KB Output is correct
2 Correct 868 ms 512324 KB Output is correct
3 Correct 1153 ms 338412 KB Output is correct
4 Correct 242 ms 20164 KB Output is correct
5 Correct 769 ms 174308 KB Output is correct
6 Correct 759 ms 174432 KB Output is correct
7 Correct 763 ms 174524 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 10 ms 5420 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 8 ms 2100 KB Output is correct
11 Correct 4 ms 972 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 885 ms 513948 KB Output is correct
14 Correct 868 ms 512324 KB Output is correct
15 Correct 1153 ms 338412 KB Output is correct
16 Correct 242 ms 20164 KB Output is correct
17 Correct 769 ms 174308 KB Output is correct
18 Correct 759 ms 174432 KB Output is correct
19 Correct 763 ms 174524 KB Output is correct
20 Correct 773 ms 174060 KB Output is correct
21 Correct 225 ms 20240 KB Output is correct
22 Correct 767 ms 174148 KB Output is correct
23 Correct 237 ms 20196 KB Output is correct
24 Correct 761 ms 174008 KB Output is correct
25 Correct 1104 ms 337820 KB Output is correct
26 Correct 861 ms 516856 KB Output is correct
27 Correct 852 ms 516896 KB Output is correct