oj.uz

Submission #469021

# Submission time Handle Problem Language Result Execution time Memory
469021 2021-08-30T12:04:18 Z wdjpng Chase (CEOI17_chase) C++17
0 / 100
 276 ms 524292 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)

using namespace std;

int n,v;
vector<int>p;
vector<vector<int>>mem;
vector<vector<pair<int, int>>>maxtakebreadcrumb1;
vector<vector<int>>maxtakebreadcrumb2;
vector<vector<pair<int, int>>>maxnotake1;
vector<vector<int>>maxnotake2;
vector<vector<int>>E;

bool comp(const pair<int, int>& a, const pair<int, int>& b) {return a>b;}
int dfs(int pos, int bc, int parent)
{
    assert(mem[pos][bc]!=-2);
    if(mem[pos][bc]!=-1) return mem[pos][bc];
    if(bc==0) return 0;
    
    int sum = 0;
    for(int w : E[pos])
    {
        if(w==parent) continue;
        sum+=p[w];
    }

    int maxx = 0;
    priority_queue<pair<int, int>>notake, take;
    notake.push({0,-1});
    take.push({0,-1});

    for(int w : E[pos])
    {
        if(w==parent) continue;
        int nt = dfs(w, bc, pos);
        int t = dfs(w, bc-1, pos) + sum;
        notake.push({-nt, w});
        take.push({-t, w});
        if (take.size()  >1) take.pop();
        if (notake.size()>1) notake.pop();
        
        maxx=max(maxx, nt);
        maxx=max(maxx, t);
    }

    maxtakebreadcrumb1[pos][bc] = take.top();
    maxnotake1[pos][bc] = notake.top();
    maxnotake1[pos][bc].first=-maxnotake1[pos][bc].first;
    maxtakebreadcrumb1[pos][bc].first=-maxtakebreadcrumb1[pos][bc].first;

    return mem[pos][bc] = maxx;
}

int mx = 0;
void meta_dfs(int pos, int parent)
{
    vector<int>oldmem = mem[pos];

    mx=max(mx, dfs(pos, v, -1));
    for(int w : E[pos])
    {
        if(w==parent) continue;
       
        //unroot root
        for(int i = 1; i <= v; i++)
        { 
            mem[pos][i] = max(maxnotake1[pos][i].first, maxtakebreadcrumb1[pos][i].first-p[w]);
            if(maxnotake1[pos][i].second==w||maxtakebreadcrumb1[pos][i].second==w)
            {
                mem[pos].assign(v+1, -1);
                break;
            }
        }

        // child as root
        mem[w].assign(v+1, -1);

        //undo
        //mem[pos].assign(v+1, -1);
        //mem.assign(n+1, vector<int>(v+1, -1));

        meta_dfs(w, pos);
    }

    mem[pos] = oldmem;
    //reroot root should not matter
    //for(int i = 1; i <= v; i++)
    //{
    //    mem[pos][i] = max(maxnotake1[pos][i].first, maxtakebreadcrumb1[pos][i].first);
    //    //assert(mem[pos][i]==oldmem[i]);
    //    mem[pos][i]=-2;
    //}
}

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

signed main()
{
    cin>>n>>v;
    p.resize(n+1);
    rep(i, n) cin>>p[i+1];

    E.resize(n+1);
    mem.assign(n+1, vector<int>(v+1, -1));

    maxtakebreadcrumb1.assign(n+1, vector<pair<int, int>>(v+1, {0, -1}));
    maxnotake1.assign(n+1, vector<pair<int, int>>(v+1, {0, -1}));
    maxtakebreadcrumb2.assign(n+1, vector<int>(v+1, 0));
    maxnotake2.assign(n+1, vector<int>(v+1, 0));

    rep(i,n-1)
    {
        int a,b;
        cin>>a>>b;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    //int maxx = dfs(1, v, -1);
    //if(n<=1000) maxx = bruteforce();
    meta_dfs(1, -1);
    cout<<mx<<"\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -