Submission #318634

#	Time	Username	Problem	Language	Result	Execution time	Memory
318634		CaroLinda	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	254 ms	30648 KiB

election_campaign

#include <bits/stdc++.h>

#define sz(x) (int)(x.size() )
#define ll long long
#define all(x) x.begin(),x.end()

const int MAXN = 1e5+10 ;
const int LOG = 20 ;

using namespace std ;

int n , m ;
int tin[MAXN] , tout[MAXN] , lvl[MAXN] ;
int dp[LOG][MAXN] ;
int dpPlan[MAXN] ;
vector<int> adj[MAXN] ;
vector<tuple<int,int,int> > myPlans[MAXN] ;

struct Bit
{
	int bit[MAXN] ;

	void upd(int pos, int val ) { for(int i = pos ;i < MAXN ; i += i&-i ) bit[i] += val ; }
	int qry(int pos )
	{
		int tot = 0 ;
		for(int i = pos ; i > 0 ; i -= i&-i ) tot += bit[i] ;
		return tot ;
	}	

} bit ;

int curTime ;
void dfs(int x)
{
	tin[x] = tout[x] = ++curTime ;

	for(auto e : adj[x] )
	{
		if(e == dp[0][x]) continue ;

		lvl[e] = lvl[x]+1 ;
		dp[0][e] = x ;   	
		dfs(e) ;

		tout[x] = tout[e] ;

	}

}

int getLca(int x, int y )
{
	if(lvl[x] < lvl[y] ) swap(x,y) ;

	for(int i = LOG-1 ; i >= 0 ; i-- )
		if( lvl[x] - (1<<i ) >= lvl[y] ) x = dp[i][x] ;

	if(x == y ) return x ;

	for(int i = LOG-1 ; i >= 0 ; i-- )
		if( dp[i][x] != -1 && dp[i][y] != dp[i][x] )
		{
			x = dp[i][x] ;
			y = dp[i][y] ;
		}

	return dp[0][x] ;

}

void calcDp(int x )
{
	int soma = 0 ;

	for(auto e : adj[x] ) 
		if(e != dp[0][x] )
		{
			calcDp(e) ;
			soma += dpPlan[e] ;
		}

	for(auto e : myPlans[x] )
	{
		int a = get<0>(e) ;
		int b = get<1>(e) ;

		a = tin[a] ;
		b = tin[b] ;

		int sominha = bit.qry(a) + bit.qry(b) + soma + get<2>(e) ;
		dpPlan[x] = max(dpPlan[x] , sominha ) ;	
	}

	dpPlan[x] = max(dpPlan[x] , soma ) ;

	bit.upd(tin[x] , soma - dpPlan[x] ) ;
	bit.upd( tout[x] + 1 , dpPlan[x] - soma ) ;

}

int main()
{

	scanf("%d", &n ) ;

	for(int i = 0 , a ,b ; i < n-1 ; i++ )
	{	
		scanf("%d %d", &a, &b ) ;

		adj[a].push_back(b) ;
		adj[b].push_back(a) ;

	}

	memset(dp,-1,sizeof dp );

	dfs(1) ;

	for(int i = 1 ; i < LOG ; i++ )
		for(int j = 1 ; j <= n ; j++ )
			if( dp[i-1][j] != -1 ) dp[i][j] = dp[i-1][dp[i-1][j]] ;

	scanf("%d", &m ) ;

	for(int i = 0 , a , b , c ; i < m ; i++ )
	{
		scanf("%d %d %d", &a, &b, &c ) ;

		myPlans[ getLca(a,b) ].push_back( make_tuple(a,b,c) ) ;

	}

	calcDp(1) ;

	printf("%d\n", dpPlan[1] ) ; 

}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |  scanf("%d", &n ) ;
      |  ~~~~~^~~~~~~~~~~
election_campaign.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |   scanf("%d %d", &a, &b ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
election_campaign.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |  scanf("%d", &m ) ;
      |  ~~~~~^~~~~~~~~~~
election_campaign.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |   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