Submission #29790

#	Time	Username	Problem	Language	Result	Execution time	Memory
29790		samir_droubi	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	396 ms	32828 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int mxn=(1e5)+5;

vector<int>tr[mxn];
int p[mxn][20];
int dep[mxn];
int T;
int in[mxn];
int out[mxn];
void dfs(int v,int pa)
{
    ++T;
    in[v] = T;
    for(int i = 0 ; i < tr[v].size() ; ++i )
    {
        int u = tr[v][i];
        if(u == pa)continue;
        
        dep[u] = dep[v] + 1;
        p[u][0] = v;

        dfs( u, v);
    }
    out[v] = T;
}
int mxlog = 0;
void init()
{
    while( ( 1<<mxlog ) <= n ) ++mxlog;
    for(int j = 1 ; j < mxlog ; ++j)
        for(int i = 1; i <= n ; ++i ) 
            p[ i ][ j ] = p[ p[ i ][ j - 1 ] ][ j - 1 ];
}
int lca(int x,int y)
{
    if( dep[x] > dep[y] ) swap( x, y);
    int dif = dep[y] - dep[x];
    for(int i = 0 ; i < mxlog ; ++i )
    {
        if( ( 1<<i ) & dif )
            y=p[y][i];
    }
    if( x == y )return x;
    for(int i = mxlog - 1 ; i >= 0 ; --i )
        if( p[x][i] != p[y][i] )
        {
            x = p[x][i];
            y = p[y][i];
        }
    return p[x][0];
}

int lz[mxn*4];
int sum[mxn];
void pros(int p,int l,int r)
{
    if(l!=r)
    {
        lz[ p * 2 ] += lz[p];
        lz[ p * 2 + 1 ] += lz[p];
    }
    else sum[l] += lz[ p ];
    lz[ p ]=0;
}
void update(int p,int l,int r,int i,int j,int x)
{
    pros( p , l , r );
    if( r < i || l > j)return;
    if( l >= i && r <= j)
    {
        lz[p] += x;
        pros( p , l , r );
        return ;
    }
    int md = ( l + r ) / 2;
    update( p * 2 , l , md , i , j , x );
    update( p * 2 + 1 , md + 1 , r , i ,j , x );

}
void get(int p,int l,int r,int i)
{
    pros( p , l , r );
    if( r < i || l > i )return;
    if( l == r ) return;
    int md = ( l + r ) / 2;
    if( i <= md )get( p * 2 , l , md , i);
    else get( p * 2 + 1 , md + 1 , r , i);
}

int dp[mxn];
int dpsm[mxn];
int ans=0;
vector< pair< int , pair< int , int > > >q[mxn];
void dfs1(int v,int pa)
{
    int sm=0;
    for(int i = 0 ; i < tr[v].size() ; ++i )
    {
        int u = tr[v][i];
        if( u == pa )continue;

        dfs1(u,v);
        sm += dp[u];

        dp[v] = max( dp[v] , dp[u] );
    }
    dpsm[v] = sm;
    
    for(int i = 0 ; i < tr[v].size() ; ++i )
    {
        int u = tr[v][i];
        if( u == pa )continue;
        update( 1 , 1 , n , in[u] , out[u] , sm - dp[u] );
    }

    for(int i = 0 ; i < q[v].size() ; ++i)
    {
        int c = q[v][i].first;
        int a = q[v][i].second.first;
        int b = q[v][i].second.second;
        
        int vl = 0;
        if( a == v)
        {

            get( 1 , 1 , n , in[b] );

            vl += sum[ in[b] ] + dpsm[ b ];
            
        }
        else if ( b == v)
        {

            get( 1 , 1 , n , in[a] );

            vl += sum[ in[a] ] + dpsm[ a ];
            
        }
        else
        {

            get( 1 , 1 , n , in[b] );

            vl += sum[ in[b] ] ;

            get( 1 , 1 , n , in[a] );

            vl += sum[ in[a] ] ;

            vl += dpsm[a] + dpsm[b];

            vl -= sm;
        }
        dp[v] = max( dp[v] , vl + c ); 
    }
    dp[v] = max( dp[v] , dpsm[v] );
    ans = max( ans , dp[v] );
}
int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n - 1 ; ++i ) 
    {
        int x , y ;
        scanf("%d%d",&x,&y);
        tr[x].push_back(y);
        tr[y].push_back(x);
    }

    dfs(1,1);
    init();

    scanf("%d",&m);
    for(int i = 0; i < m ; ++i )
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        int node = lca( x , y );
        q[node].push_back( { c , { x , y } } ); 
    }

    dfs1(1,1);
    printf("%d\n",ans);

    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < tr[v].size() ; ++i )
                       ^
election_campaign.cpp: In function 'void dfs1(int, int)':
election_campaign.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < tr[v].size() ; ++i )
                       ^
election_campaign.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < tr[v].size() ; ++i )
                       ^
election_campaign.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < q[v].size() ; ++i)
                       ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:163:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
election_campaign.cpp:167:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^
election_campaign.cpp:175:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&m);
                   ^
election_campaign.cpp:179:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x,&y,&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