Submission #224684

#	Time	Username	Problem	Language	Result	Execution time	Memory
224684		DodgeBallMan	Election Campaign (JOI15_election_campaign)	C++14	30 / 100	1095 ms	23800 KiB

election_campaign

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

using namespace std;

const int N = 1e5 + 10;

vector<iii> path[N];
vector<int> g[N], t[2];
int sz[N], par[N], dp[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 );
}

int query( vector<int> &t, int l, int r ) {
   int ret1 = 0, ret2 = 0;
   for( int i = r ; i > 0 ; i -= i & -i ) ret1 += t[i];
   for( int i = l-1 ; i > 0 ; i -= i & -i ) ret2 += t[i];
   return ret1 - ret2; 
}

void update( vector<int> &t, int x, int va ) { for( int i = x ; i < N ; i += i & -i ) t[i] += va; }

int queryhld( int ty, int a, int b ) {
    int 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 ) {
    for( int v : g[u] ) if( v != p ) {
        solve( v, u );
        dp[u] += dp[v];
    }   
    update( t[0], pos[u], dp[u] );
    for( iii x : path[u] ) {
        int a, b, 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] );
}

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, c ; i <= q ; i++ ) {
        scanf("%d %d %d",&a,&b,&c);
        int x = lca( a, b );
        path[x].emplace_back( a, b, c );
    }
    solve( 1, 0 );
    printf("%d",dp[1]);
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
election_campaign.cpp:78: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:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
election_campaign.cpp:84: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: 0 / 30
• Subtask 5: 10 / 10
• Subtask 6: 0 / 40