Submission #224676

#	Time	Username	Problem	Language	Result	Execution time	Memory
224676		DodgeBallMan	Election Campaign (JOI15_election_campaign)	C++14	30 / 100	1094 ms	30468 KiB

election_campaign

#include <bits/stdc++.h>
#define iii tuple<int, int, long long>

using namespace std;

const int N = 1e5 + 10;

vector<iii> path[N];
vector<int> g[N];
vector<long long> t[2];
long long dp[N];
int sz[N], par[N], dep[N], rot[N], pos[N], n, q;

void dfs( int u, int p ) {
    if( p != 0 ) g[u].erase( find( g[u].begin(), g[u].end(), p ) );
    par[u] = p, sz[u] = 1, dep[u] = dep[p] + 1;
    for( int v : g[u] ) if( v != p ) {
        dfs( v, u );
        if( sz[v] > sz[g[u][0]] ) swap( v, g[u][0] );
    }
}

void hld( int u ) {
    static int idx = 0;
    if( par[u] == 0 || g[par[u]][0] != u ) rot[u] = u;
    else rot[u] = rot[par[u]];
    pos[u] = ++idx;
    for( int v : g[u] ) hld( v );
}

long long query( vector<long long> &t, int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
    if( l > rr || r < ll ) return 0;
    if( l >= ll && r <= rr ) return t[idx];
    int mid = l + r >> 1;
    return query( t, ll, rr, l, mid, idx<<1 ) + query( t, ll, rr, mid+1, r, idx<<1|1 );
}

void update( vector<long long> &t, int x, long long va, int l = 1, int r = n, int idx = 1 ) {
    //printf("%d %d %d\n",l,r,x);
    if( l > x || r < x ) return ;
    if( l == r ) return void( t[idx] = va );
    int mid = l + r >> 1;
    update( t, x, va, l, mid, idx<<1 ), update( t, x, va, mid+1, r, idx<<1|1 );
    t[idx] = t[idx<<1] + t[idx<<1|1];
}

long long queryhld( int ty, int a, int b ) {
    long long ret = 0;
    while( rot[a] != rot[b] ) {
        if( dep[rot[a]] < dep[rot[b]] ) swap( a, b );
        ret += query( t[ty], pos[rot[a]], pos[a] );
        a = par[rot[a]];
    }
    if( dep[b] < dep[a] ) swap( a, b );
    ret += query( t[ty], pos[a], pos[b] );
    return ret;
}

int lca( int a, int b ) {
     while( rot[a] != rot[b] ) {
        if( dep[rot[a]] < dep[rot[b]] ) swap( a, b );
        a = par[rot[a]];
    }
    if( dep[b] < dep[a] ) return b;
    else return a;
}

void solve( int u, int p ) {
    //printf("%d %d\n",u,p);
    for( int v : g[u] ) if( v != p ) {
        solve( v, u );
        dp[u] += dp[v];
    }   
    update( t[0], pos[u], dp[u] );
    //printf("HH");
    for( iii x : path[u] ) {
        int a, b;
        long long c;
        tie( a, b, c ) = x;
        dp[u] = max( dp[u], c + queryhld( 0, a, b ) - queryhld( 1, a, b ) );
    }
    update( t[1], pos[u], dp[u] );
    //printf("U: %d %lld\n",u,dp[u]);
}

int main()
{
    t[0].resize( 4*N ), t[1].resize( 4*N );
    scanf("%d",&n);
    for( int i = 1, a, b ; i < n ; i++ ) {
        scanf("%d %d",&a,&b);
        g[a].emplace_back( b ), g[b].emplace_back( a );
    }
    dfs( 1, 0 ), hld( 1 );
    scanf("%d",&q);
    for( int i = 1, a, b ; i <= q ; i++ ) {
        long long c;
        scanf("%d %d %lld",&a,&b,&c);
        int x = lca( a, b );
        path[x].emplace_back( a, b, c );
        //printf("%d %d %d\n",x,a,b);
    }
    solve( 1, 0 );
    printf("%lld",dp[1]);
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'long long int query(std::vector<long long int>&, int, int, int, int, int)':
election_campaign.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
election_campaign.cpp: In function 'void update(std::vector<long long int>&, int, long long int, int, int, int)':
election_campaign.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
election_campaign.cpp:91: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:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
election_campaign.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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