Submission #1168032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168032		lampooppp	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	322 ms	36148 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

const int N=1e5;
vector<int> adj[N+1];
int la[N+1], cl[N+1];
int vis[N+1],chi[N+1];
int pa[N+1],n,m,id[N+1],h[N+1];
int l[N+1], r[N+1], c[N+1];
int up[N+1][20];
vector<int> que[N+1];
pair<int,int> d1chi[N+1];
int mx[N+1];
int sum[N+1];
int st[4*N+1][2];

void dfs(int u)
{
    chi[u]=1;
    cl[u]=0;
    vis[u]=1;
    for(int v : adj[u])
    {
        if(vis[v]) continue;
        pa[v]=u;
        h[v]=h[u]+1;
        up[v][0]=u;
        for(int i=1;i<20;++i) up[v][i] = up[up[v][i-1]][i-1];
        dfs(v);
        chi[u]+=chi[v];
        cl[u]+=cl[v];
        cl[u]%=2;
    }
    if(adj[u].size()==1)
        cl[u]=1;
    //cout << u << " "
}

int chead[N+1], cid[N+1], pos[N+1], ch=1, tme=0;

void hld(int u)
{
    cid[u]=ch;
    pos[u]=++tme;
    id[tme]=cl[u];
    int mx=0;
    int k;
    for(int v : adj[u])
    {
        if(v==pa[u]) continue;
        if(mx<chi[v])
        {
            mx=chi[v];
            k=v;
        }
    }
    if(mx==0) return;
    hld(k);
    for(int v : adj[u])
    {
        if(v==k || v==pa[u]) continue;
        ch++;
        chead[ch]=v;
        hld(v);
    }
}

void update(int x, int low, int hi, int i, int k, int p)
{
    if(low==hi)
    {
        st[x][p]=k;
        return;
    }
    int mid=low+hi>>1;
    if(i<=mid) update(x*2,low,mid,i,k,p);
    else update(x*2+1,mid+1,hi,i,k,p);
    st[x][p] = st[x*2][p] + st[x*2+1][p];
}

int get(int x, int low, int hi, int i, int j ,int p)
{
    if(low > hi || low > j || hi<i) return 0;
    if(low>=i && hi<=j) return st[x][p];
    int mid=low+hi>>1;
    return get(x*2,low,mid,i,j,p) + get(x*2+1,mid+1,hi,i,j,p);
}

int lca(int u, int v, int i)
{
    if(h[u]>h[v])
    {
        int tmp = u;
        int k = h[u]-h[v];
        for(int i=0;i<20;++i)
            if(k>>i&1) u=up[u][i];
       // cout << "UU";
        if(u==v)
        {
            k--;
            for(int i=0;i<20;++i)
                if(k>>i&1) tmp=up[tmp][i];
            d1chi[i] = {tmp,-1} ;
            return u;
        }
    }
    else
    {
        int tmp=v;
        int k = h[v]-h[u];
        for(int i=0;i<20;++i)
            if(k>>i&1) v=up[v][i];
        if(u==v)
        {
            k--;
            for(int i=0;i<20;++i)
                if(k>>i&1) tmp=up[tmp][i];
            d1chi[i] = {-1,tmp} ;
            return u;
        }
    }
    int k = __lg(h[u]);
    for(; k>=0; k--)
    {
        if(up[u][k] !=up[v][k])
        {
            u=up[u][k];
            v=up[v][k];
        }
    }
    d1chi[i] = {u,v};
    return up[u][0];
}

int gettree(int u, int v, int p)
{
    if(u==-1) return 0;
    int res=0;
    while(cid[u]!=cid[v])
    {
        res+=get(1,1,n,pos[chead[cid[v]]],pos[v],p);
        v=pa[chead[cid[v]]];
    }
    return res + get(1,1,n,pos[u],pos[v],p);
}


void solve(int u)
{
    bool la = 1;
    for(int v : adj[u])
    {
        if(v==up[u][0]) continue;
        la=0;
        solve(v);
        sum[u] +=mx[v];
    }
    if(la)
    {
        for(int i : que[u])
        {
            mx[u] =max(mx[u] , c[i]);
        }
        update(1,1,n,pos[u],mx[u],0);
        //update(1,1,n,pos[u],mx[i]);
    }
    else
    {
        mx[u] = sum[u];
        for(int i : que[u])
        {
            int x = gettree(d1chi[i].first,l[i],0);
            int y = gettree(d1chi[i].second,r[i],0);
            int z = gettree(d1chi[i].first,l[i],1);
            int t = gettree(d1chi[i].second,r[i],1);
            mx[u] = max(mx[u],sum[u] + z+t-x-y+c[i]);
        }
        update(1,1,n,pos[u],mx[u],0);
        update(1,1,n,pos[u],sum[u],1);
    }
    //cout << u << " " << mx[u] << '\n';
}

int main()
{
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
    cin >> n;
    for(int i=1;i<n;++i)
    {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    h[1]=1;
    dfs(1);
    chead[1]=1;
    hld(1);
    int m;
    cin >> m;
    for(int i=1;i<=m;++i)
    {
        cin >> l[i] >> r[i] >> c[i];
        int x = lca(l[i],r[i],i);
        que[x].push_back(i);
        //cout << x << '\n';
    }
    solve(1);
    cout << mx[1];
    //build(1,1,n);

}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40