Submission #469026

#	Time	Username	Problem	Language	Result	Execution time	Memory
469026		wdjpng	Chase (CEOI17_chase)	C++17	0 / 100	279 ms	524292 KiB

chase

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30