Submission #85824

#	Time	Username	Problem	Language	Result	Execution time	Memory
85824		rzbt	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	275 ms	152484 KiB

election_campaign

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

int n,m,vreme;
vector<int> niz[MAXN];
vector<pair<int,int> > ono;
pair<int,int> seg[8*MAXN];
int ulaz[MAXN],izlaz[MAXN];
ll dp[MAXN][2];

struct put{
    int a,b,c;

};
vector<put> svi[MAXN];
put make_put(int a,int b,int c){
    put p;
    p.a=a;
    p.b=b;
    p.c=c;
    return p;
}


void dfs1(int t,int o,int h){
    vreme++;
    ulaz[t]=vreme;
    ono.pb(mp(h,t));
    for(auto x:niz[t]){
        if(x==o)continue;
        dfs1(x,t,h+1);
        ono.pb(mp(h,t));
        vreme++;
    }
}
void izgradi(int l,int d,int k){

    if(l==d){
        seg[k]=ono[l];
        return;
    }
    int mid=(l+d)/2;
    izgradi(l,mid,k+k);
    izgradi(mid+1,d,k+k+1);
    seg[k]=min(seg[k+k],seg[k+k+1]);
}

pair<int,int> dobij(int l,int d,int tl,int td,int k){

    if(l>td || d<tl)return ono[0];
    if(l>=tl && d<=td)return seg[k];
    int mid=(l+d)/2;
    return min(dobij(l,mid,tl,td,k+k),dobij(mid+1,d,tl,td,k+k+1));
}


ll bit[MAXN];
void dod(int p, ll x){

    for(;p<MAXN;p+=(-p)&p)
        bit[p]+=x;
}
ll dob(ll p){

    ll z=0;
    for(;p>0;p-=(-p)&p)
        z+=bit[p];
    return z;
}


void dfs(int t,int o){
    vreme++;
    ulaz[t]=vreme;
    for(auto x:niz[t]){
        if(x==o)continue;
        dfs(x,t);
        dp[t][0]+=dp[x][1];
    }
    for(auto x:niz[t]){
        if(x==o)continue;
        dod(ulaz[x],dp[t][0]-dp[x][1]);
        dod(izlaz[x]+1,-dp[t][0]+dp[x][1]);
    }
    dp[t][1]=dp[t][0];
    for(auto x:svi[t]){
        dp[t][1]=max(dp[t][1],dob(ulaz[x.a])+dob(ulaz[x.b])+dp[x.a][0]+dp[x.b][0]+x.c-dp[t][0]);
        //printf("          %d   %lld %lld     %d  %d\n",t,dob(ulaz[x.a]),dob(ulaz[x.b]),x.a,x.b);

    }
    //printf("   %d   %lld %lld\n",t,dp[t][0],dp[t][1]);

    izlaz[t]=vreme;
}


int main()
{
    scanf("%d", &n);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d %d", &a, &b);
        niz[a].pb(b);
        niz[b].pb(a);
    }
    ono.pb(mp(MAXN,0));
    dfs1(1,0,0);
    izgradi(1,n+n-1,1);
    scanf("%d", &m);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        if(ulaz[a]>ulaz[b])swap(a,b);

        //printf("%d\n",dobij(1,n+n-1,ulaz[a],ulaz[b],1).second);
        svi[dobij(1,n+n-1,ulaz[a],ulaz[b],1).second].pb(make_put(a,b,c));
    }
    vreme=0;
    memset(ulaz,0,sizeof(ulaz));

    dfs(1,0);
    printf("%lld",dp[1][1]);

    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
election_campaign.cpp:111: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:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
election_campaign.cpp:121: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