Submission #231922

#	Time	Username	Problem	Language	Result	Execution time	Memory
231922		nicolaalexandra	Chase (CEOI17_chase)	C++14	0 / 100	4065 ms	42848 KiB

chase

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
vector <int> L[DIM];
int v[DIM],sum[DIM],first[DIM],level[DIM],fth[DIM],E[DIM*4],p[DIM*4];
pair <int,int> rmq[20][DIM*4],dp[DIM];
int n,x,y,i,j,nr,k;
void dfs (int nod, int tata){

    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[tata];
    fth[nod] = tata;
    dp[nod].first = dp[tata].first + sum[nod];
    dp[nod].second = dp[tata].second - v[nod];
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            E[++k] = nod;
        }
}
int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy-posx+1];
    pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]);
    return E[sol.second];
}

int get_sum (int x, int y){
    if (level[x] < level[y])
        return 0;
    return dp[x].second - dp[y].second;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>nr;
    for (i=1;i<=n;i++)
        cin>>v[i];
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (i=1;i<=n;i++){
        sum[i] = v[i];
        for (auto it : L[i])
            sum[i] += v[it];
    }

    dfs (1,0);

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);

    for (i=1;(1<<i)<=k;i++){
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }}
    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;


    /// nu inteleg enuntu asa ca o sa fac brut sa vad daca asa e
    int maxi = 0;
    for (i=1;i<=n;i++){
        for (j=i+1;j<=n;j++){
            int lca = get_lca (i,j);
            if (level[i] + level[j] - 2*level[lca] + 1 > nr)
                continue;

            int val = dp[i].first - dp[lca].first + dp[j].first - dp[lca].first + sum[lca];

            val -= v[i];
            val -= v[j];

            val -= 2 * get_sum (fth[i],lca);
            val -= 2 * get_sum (fth[j],lca);

            if (i != lca && j != lca)
                val -= v[lca];

            if (val - min(v[i],v[j]) > maxi)
                maxi = val - min(v[i],v[j]);
        }
    }

    cout<<maxi;




    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30