Submission #116397

#	Time	Username	Problem	Language	Result	Execution time	Memory
116397		JohnTitor	Chase (CEOI17_chase)	C++11	100 / 100	574 ms	253528 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Chase"
const ll inf=1e18;
ll p[100001];
ll pp[100001];
ll c[100001];
vector <int> g[100001];
ll f[100001][101][2];
ll h[100001][101];
void update(ll *p, ll a){
    if(p[0]<a){
        p[1]=p[0];
        p[0]=a;
    }
    else if(p[1]<a) p[1]=a;
}
bool done[100001];
int n, k;
ll ans=0;
deque <int> order;
void dfs(int u){
    done[u]=1;
    for(int &v: g[u]) if(done[v]){
        swap(v, g[u].back());
        g[u].pop_back();
        break;
    }
    for(int v: g[u]) c[u]+=p[v];
    for(int v: g[u]){
        pp[v]=p[u];
        dfs(v);
        FOR(i, 1, k) f[v][i][0]=max(f[v][i][0], f[v][i-1][0]);
        FOR(i, 0, k) update(f[u][i], max(f[v][i][0], (i?f[v][i-1][0]:-inf)+c[v]));
        FOR(i, 1, k) h[v][i]=max(h[v][i], h[v][i-1]);
        FOR(i, 0, k) h[u][i]=max(h[u][i], max(h[v][i], (i?h[v][i-1]:-inf)+c[u]-p[v]+pp[u]));
    }
    h[u][1]=max(h[u][1], c[u]+pp[u]);
    FOR(i, 0, k){
        ans=max(ans, h[u][i]);
        ans=max(ans, f[u][i][0]);
        if(i) ans=max(ans, f[u][i-1][0]+c[u]+pp[u]);
    }
    for(int v: g[u]){
        FOR(i, 0, k){
            int j=k-i;
            if(f[u][i][0]==max(f[v][i][0], (i?f[v][i-1][0]:-inf)+c[v])){
                ans=max(ans, f[u][i][1]+max(h[v][j], (j?h[v][j-1]:-inf)+c[u]-p[v]+pp[u]));
            }
            else{
                ans=max(ans, f[u][i][0]+max(h[v][j], (j?h[v][j-1]:-inf)+c[u]-p[v]+pp[u]));
            }
        }
    }
//    bug(u);
//    FOR(i, 0, k) cerr<<h[u][i]<<" \n"[i==k];
//    FOR(i, 0, k) cerr<<f[u][i][0]<<" \n"[i==k];
//    FOR(i, 0, k) cerr<<f[u][i][1]<<" \n"[i==k];
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(k);
    FOR(i, 1, n) read(p[i]);
    {
        int u, v;
        FFOR(i, 1, n){
            read(u);
            read(v);
            g[u].pb(v);
            g[v].pb(u);
        }
    }
    dfs(1);
    writeln(ans);
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30