답안 #116360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116360 2019-06-12T10:40:25 Z JohnTitor Chase (CEOI17_chase) C++11
30 / 100
371 ms 169228 KB
#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;
int p[100001];
int 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, 1, k) h[v][i]=max(h[v][i], h[v][i-1]);
        FOR(i, 0, k) update(f[u][i], max(f[v][i][0], (i?f[v][i-1][0]:-inf)+c[v]));
//        FOR(i, 0, k) 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]));
//            }
//        }
//    }
}
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);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 314 ms 169228 KB Output is correct
2 Correct 324 ms 169140 KB Output is correct
3 Correct 239 ms 165360 KB Output is correct
4 Correct 233 ms 165792 KB Output is correct
5 Correct 329 ms 165752 KB Output is correct
6 Correct 371 ms 165964 KB Output is correct
7 Correct 349 ms 165812 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -