oj.uz

Submission #469103

# Submission time Handle Problem Language Result Execution time Memory
469103 2021-08-30T18:00:55 Z wdjpng Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 497712 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2,avx,fma")
//#pragma GCC target ("native")
    
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i = 0; i < n; i++)
    
using namespace std;
    
int n,v;
vector<int>p;
vector<vector<ll>>mem;
vector<vector<signed>>E;

signed takei[100001][101];
signed notakei[100001][101];
ll takemaxx[100001][101];
ll notakemaxx[100001][101];
ll takealtmaxx[100001][101];
ll notakealtmaxx[100001][101];


ll dfs(int pos, int bc, int parent)
{
    if(parent!=-1&&mem[pos][bc]!=-1) return mem[pos][bc];
    if(bc==0) return 0;
        
    ll sum = 0;
    for(const int& w : E[pos])
    {
        if(w==parent) continue;
        sum+=p[w];
    }

    ll maxx = 0;
    takemaxx[pos][bc]=0;
    takei[pos][bc] = -1;
    notakemaxx[pos][bc]=0;
    notakei[pos][bc] = -1;

    ll t, nt;
    for(const int& w : E[pos])
    {
        if(w==parent) continue;
        nt = dfs(w, bc, pos);
        t = dfs(w, bc-1, pos) + sum;

        if(nt>notakemaxx[pos][bc])
        {
            notakei[pos][bc] = w;
            notakemaxx[pos][bc] = nt;
        }

        if(t>takemaxx[pos][bc])
        {
            takei[pos][bc] = w;
            takemaxx[pos][bc] = t;
        }

        maxx=max(maxx, nt);
        maxx=max(maxx, t);
    }

    takealtmaxx[pos][bc]  = 0;
    notakealtmaxx[pos][bc]=0;

    for(const int& w : E[pos])
    {
        if(w==parent) continue;
        nt = dfs(w, bc, pos);
        t = dfs(w, bc-1, pos) + sum;
        if(takei[pos][bc]!=-1&&takei[pos][bc]!=w)
        {
            takealtmaxx[pos][bc]=max(takealtmaxx[pos][bc], t);
        }
        if(notakei[pos][bc]!=-1&&notakei[pos][bc]!=w)
        {
            notakealtmaxx[pos][bc]=max(notakealtmaxx[pos][bc], nt);
        }
    }

    return mem[pos][bc] = maxx;
}
    
ll bruteforce()
{
    ll maxx=0;
    rep(i, n) 
    {
        mem.assign(n+1, vector<ll>(v+1, -1));
        maxx=max(maxx, dfs(i+1, v, -1));
    }
    return maxx;
}

ll mx=0;
void meta_dfs(int pos, int parent)
{
    rep(i, v+1) mx = max(mx, dfs(pos, i, -1));
    for(const int& w : E[pos])
    {
        if(w==parent) continue;
        for(int i = 1; i<= v; i++)
        {
            mem[pos][i] = 0;
            if(takei[pos][i]!=w) mem[pos][i] = max(mem[pos][i], takemaxx[pos][i]-p[w]);
            else mem[pos][i] = max(mem[pos][i], takealtmaxx[pos][i]-p[w]);
            if(notakei[pos][i]!=w) mem[pos][i] = max(mem[pos][i], notakemaxx[pos][i]);
            else mem[pos][i] = max(mem[pos][i], notakealtmaxx[pos][i]);
        }
        meta_dfs(w,pos);
    }
}
//
//void dfs2(int pos, int par)
//{
//    int sum = 0;
//    for(int w : E[pos])
//    {
//        sum+=p[w];
//        if(w!=par) dfs2(w,pos);
//    }
//    totsum[pos]=sum;
//}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>v;
    p.resize(n+1);
    rep(i, n) cin>>p[i+1];
    
    E.resize(n+1);
    
    rep(i,n-1)
    {
        signed a,b;
        cin>>a>>b;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    //dfs2(1,-1);
    //int maxx = dfs(1, v, -1);
    //if(n<=1000) maxx = bruteforce();
    //cout<<maxx<<"\n";
    
    mem.assign(n+1, vector<ll>(v+1, -1));
    

    meta_dfs(1, -1);
    cout<<mx<<"\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 14 ms 5324 KB Output is correct
8 Correct 4 ms 4556 KB Output is correct
9 Correct 3 ms 4428 KB Output is correct
10 Correct 19 ms 5196 KB Output is correct
11 Correct 6 ms 4556 KB Output is correct
12 Correct 4 ms 4428 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3841 ms 497712 KB Output is correct
2 Correct 3886 ms 497596 KB Output is correct
3 Correct 1726 ms 484068 KB Output is correct
4 Correct 312 ms 407000 KB Output is correct
5 Execution timed out 4125 ms 483792 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 14 ms 5324 KB Output is correct
8 Correct 4 ms 4556 KB Output is correct
9 Correct 3 ms 4428 KB Output is correct
10 Correct 19 ms 5196 KB Output is correct
11 Correct 6 ms 4556 KB Output is correct
12 Correct 4 ms 4428 KB Output is correct
13 Correct 3841 ms 497712 KB Output is correct
14 Correct 3886 ms 497596 KB Output is correct
15 Correct 1726 ms 484068 KB Output is correct
16 Correct 312 ms 407000 KB Output is correct
17 Execution timed out 4125 ms 483792 KB Time limit exceeded
18 Halted 0 ms 0 KB -