Submission #248680

#	Time	Username	Problem	Language	Result	Execution time	Memory
248680		Lawliet	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	284 ms	31616 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;
const int MAXN = 100010;

class FenwickTree
{
	public:

		void update(int i, int v)
		{
			for( ; i > 0 ; i -= i & -i)
				BIT[i] += v;
		}

		int query(int i)
		{
			int ans = 0;

			for( ; i < MAXN ; i += i & -i)
				ans += BIT[i];

			return ans;
		}

		void update(int L, int R, int v)
		{
			update( R , v );
			update( L - 1 , -v );
		}

		FenwickTree() { memset( BIT , 0 , sizeof(BIT) ); }

	private:

		int BIT[MAXN];
};

int n, m;
int curTime;

int depth[MAXN];
int tab[LOG][MAXN];
int dp[MAXN], f[MAXN];
int tin[MAXN], tout[MAXN];
int A[MAXN], B[MAXN], C[MAXN];

vector<int> adj[MAXN];
vector<int> groupLCA[MAXN];

FenwickTree sumDP, sumF;

void DFSInit(int cur, int p)
{
	tab[0][cur] = p;
	tin[cur] = ++curTime;
	depth[cur] = depth[p] + 1;

	for(int k = 1 ; k < LOG ; k++)
		tab[k][cur] = tab[k - 1][ tab[k - 1][cur] ];

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
		if( adj[cur][i] != p ) DFSInit( adj[cur][i] , cur );

	tout[cur] = curTime;
}

void DFSCalculate(int cur, int p)
{
	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		DFSCalculate( viz , cur );
		f[cur] += dp[viz];
	}

	dp[cur] = f[cur];

	for(int i = 0 ; i < (int)groupLCA[cur].size() ; i++)
	{
		int ind = groupLCA[cur][i];

		int curAns = C[ind] + f[cur];
		curAns += sumF.query( tin[ A[ind] ] ) - sumDP.query( tin[ A[ind] ] );
		curAns += sumF.query( tin[ B[ind] ] ) - sumDP.query( tin[ B[ind] ] );

		dp[cur] = max( dp[cur] , curAns );
	}

	sumF.update( tin[cur] , tout[cur] , f[cur] );
	sumDP.update( tin[cur] , tout[cur] , dp[cur] );
}

int LCA(int A, int B)
{
	if( depth[A] < depth[B] ) swap( A , B );

	int d = depth[A] - depth[B];

	for(int k = 0 ; k < LOG ; k++)
		if( d & (1 << k) ) A = tab[k][A];

	if( A == B ) return A;

	for(int k = LOG - 1 ; k >= 0 ; k--)
	{
		if( tab[k][A] != tab[k][B] )
		{
			A = tab[k][A];
			B = tab[k][B];
		}
	}

	return tab[0][A];
}

int main()
{
	scanf("%d",&n);

	for(int i = 1 ; i < n ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		adj[U].push_back( V );
		adj[V].push_back( U );
	}

	DFSInit( 1 , 1 );

	scanf("%d",&m);

	for(int i = 1 ; i <= m ; i++)
	{
		scanf("%d %d %d",&A[i],&B[i],&C[i]);

		int L = LCA( A[i] , B[i] );
		groupLCA[L].push_back( i );
	}

	DFSCalculate( 1 , 1 );

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

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
election_campaign.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~
election_campaign.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
election_campaign.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&A[i],&B[i],&C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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