Submission #78110

#	Time	Username	Problem	Language	Result	Execution time	Memory
78110		nxteru	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	377 ms	108716 KiB

election_campaign

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define PB push_back
struct que{int a,b,c;};
int n,m,k,par[100005],sz[100005],dp[100005],hv[100005],vs[100005],id[100005],hd[100005],cn[100005],seg[1<<18],t[100005];
vector<int>g[100005];
vector<que>q[100005];
void dfs1(int v,int p){
    sz[v]=1;
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(u!=p){
            dfs1(u,v);
            if(hv[v]==-1||sz[hv[v]]<sz[u])hv[v]=u;
            sz[v]+=sz[u];
        }
    }
}
void dfs2(int v,int p,int d,int h){
    par[k]=p;
    dp[k]=d;
    vs[k]=v;
    hd[k]=h;
    cn[k]=cn[h];
    id[v]=k++;
    if(hv[v]!=-1)dfs2(hv[v],v,d+1,h);
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(u!=p&&u!=hv[v]){
            cn[k]=id[v];
            dfs2(u,v,d+1,k);
        }
    }
}
void add(int a,int x){
    a+=(1<<17)-1;
    seg[a]+=x;
    while(a>0){
        a=(a-1)/2;
        seg[a]=seg[a*2+1]+seg[a*2+2];
    }
}
int sum(int a,int b,int l,int r,int o){
    if(r<a||b<l)return 0;
    if(a<=l&&r<=b)return seg[o];
    return sum(a,b,l,(l+r-1)/2,o*2+1)+sum(a,b,(l+r+1)/2,r,o*2+2);
}
int lca(int v,int u){
    while(hd[v]!=hd[u]){
        if(dp[hd[v]]<dp[hd[u]])swap(u,v);
        v=cn[v];
    }
    if(dp[v]<dp[u])swap(u,v);
    return u;
}
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n;i++)hv[i]=-1;
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[--a].PB(--b);
        g[b].PB(a);
    }
    dfs1(0,-1);
    dfs2(0,-1,0,0);
    for(int i=0;i<n;i++)q[i].PB(que{i,i,0});
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a=id[a-1];
        b=id[b-1];
        int l=lca(a,b);
        q[l].PB(que{a,b,c});
    }
    for(int i=n-1;i>=0;i--){
        int e=0;
        for(int j=0;j<q[i].size();j++){
            int a=q[i][j].a,b=q[i][j].b,c=q[i][j].c,s=0;
            while(hd[a]!=hd[i]){
                s+=sum(hd[a],a,0,(1<<17)-1,0);
                a=cn[a];
            }
            s+=sum(i,a,0,(1<<17)-1,0);
            while(hd[b]!=hd[i]){
                s+=sum(hd[b],b,0,(1<<17)-1,0);
                b=cn[b];
            }
            if(b!=i)s+=sum(i+1,b,0,(1<<17)-1,0);
            e=max(e,s+c);
        }
        t[i]=e;
        add(i,-e);
        if(par[i]!=-1)add(id[par[i]],e);
    }
    printf("%d\n",t[0]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs1(int, int)':
election_campaign.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs2(int, int, int, int)':
election_campaign.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<q[i].size();j++){
                     ~^~~~~~~~~~~~
election_campaign.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
election_campaign.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&m);
     ~~~~~^~~~~~~~~
election_campaign.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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