oj.uz

Submission #116389

# Submission time Handle Problem Language Result Execution time Memory
116389 2019-06-12T11:28:24 Z JohnTitor Chase (CEOI17_chase) C++11
40 / 100
 4000 ms 249516 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;
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;
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[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]));
//            }
//        }
//    }
}
void add_edge(int u){
    for(int v: g[u]) add_edge(v);
    for(int v: g[u]) g[v].pb(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);
    ll myans=ans;
    FOR(i, 2, n){
        add_edge(i-1);
        FOR(j, 1, n) FOR(x, 0, k) f[j][x][0]=f[j][x][1]=0;
        FOR(i, 1, n) done[i]=0;
        FOR(i, 1, n) c[i]=0;
        FOR(i, 1, n) pp[i]=0;
        FOR(j, 1, n) FOR(x, 0, k) h[j][x]=0;
        dfs(i);
    }
//    if(ans!=myans){
//        while(true){
//            int k;
//            writeln(k);
//        }
//    }
//    else
    writeln(ans);
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:93:8: warning: unused variable 'myans' [-Wunused-variable]
     ll myans=ans;
        ^~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 766 ms 5240 KB Output is correct
8 Correct 91 ms 5248 KB Output is correct
9 Correct 71 ms 5192 KB Output is correct
10 Correct 799 ms 5224 KB Output is correct
11 Correct 297 ms 5192 KB Output is correct
12 Correct 127 ms 5292 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4115 ms 249516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 766 ms 5240 KB Output is correct
8 Correct 91 ms 5248 KB Output is correct
9 Correct 71 ms 5192 KB Output is correct
10 Correct 799 ms 5224 KB Output is correct
11 Correct 297 ms 5192 KB Output is correct
12 Correct 127 ms 5292 KB Output is correct
13 Execution timed out 4115 ms 249516 KB Time limit exceeded
14 Halted 0 ms 0 KB -