Submission #152903

#	Time	Username	Problem	Language	Result	Execution time	Memory
152903		bvd	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	709 ms	44664 KiB

election_campaign

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define int long long
using namespace std;
const int maxn = 100000;
const int maxh = 20;
const int root = 1;
int n,m;
vector<int> adj[maxn+1];
vector<int> pathWithTop[maxn+1];

int parentOf[maxn+1][maxh+1];
int directParent[maxn+1];
int a[maxn+1],b[maxn+1],c[maxn+1];
int cnt;
int num[maxn+1],fin[maxn+1],vertex[maxn+1];

int nChain;
int chainHead[maxn+1];
int chainInd[maxn+1];
int posInBase[maxn+1];
int nBase;
int nChild[maxn+1];

int sumOfDP[maxn+1],sumOfChildrenDP[maxn+1]; // store the sum of dp

int dp[maxn+1],dpChildren[maxn+1];

/**
 * Code for HLD is adapted from http://vnoi.info/wiki/algo/data-structures/heavy-light-decomposition
 * Code for BIT is adapted from http://ntucoder.net/Blog/Details/17
 */
void hld(int u)
{
	if (chainHead[nChain]==0)
		chainHead[nChain] = u;
		
	chainInd[u] = nChain;
	nBase++;
	posInBase[u] = nBase;
	
	int mxVtx = -1;
	
	for (int v : adj[u])
		if (v!=directParent[u])
		{
			if (mxVtx == -1 or nChild[v] > nChild[mxVtx])
				mxVtx = v;
		}
	
	if (mxVtx != -1)
		hld(mxVtx);
	
	for (int v : adj[u])
	{
		if (v!=directParent[u] and v!=mxVtx)
		{
			nChain++;
			hld(v);
		}
	}
}

void updateBIT(int *bit, int x,int y)
{
	for (; x<=n; x+=x&(-x))
		bit[x]+=y;
}

void update(bool isSumOfChildrenDP, int u, int value) 
{
	if (isSumOfChildrenDP)
		updateBIT(sumOfChildrenDP,posInBase[u],value);
	else
		updateBIT(sumOfDP,posInBase[u],value);
}

int getBIT(int *bit,int x)
{ 
	int res = 0;
	for (; x>0; x-=x&(-x))
		res+=bit[x];
	return res;
}

int get(bool isSumOfChildrenDP,int l,int r)
{
	if (isSumOfChildrenDP)
		return getBIT(sumOfChildrenDP,r) - getBIT(sumOfChildrenDP,l-1);
	else
		return getBIT(sumOfDP,r) - getBIT(sumOfDP,l-1);
}

/**
 * Precondition: a is an ancestor of u
 */
int getHLD(bool isSumOfChildrenDP,int u,int a)
{
	int uchain = chainInd[u], achain = chainInd[a];
	int res = 0;
    while (1) {
          if (uchain == achain) {
               res+=get(isSumOfChildrenDP, posInBase[a], posInBase[u]);
               return res;
          }
          
          res+=get(isSumOfChildrenDP, posInBase[chainHead[uchain]], posInBase[u]);

          u = directParent[chainHead[uchain]];
          uchain = chainInd[u];
     }
}

void dfs(int x)
{
	cnt++;
	num[x] = cnt;
	vertex[cnt] = x;
	nChild[x] = 1;
	for (int y : adj[x])
	{
		if (num[y]==0)
		{
			directParent[y] = x;
			dfs(y);
			nChild[x]+=nChild[y];
		}
	}
	fin[x] = cnt;
}

bool isParent(int x,int y)
{
	return (num[x]<=num[y] and fin[y]<=fin[x]);
}

int calcParentOf(int x,int y)
{
	if (parentOf[x][y]!=-1)
		return parentOf[x][y];
	
	if (x==root)
		return parentOf[x][y] = root;
	
	if (y==0)
		return parentOf[x][y] = directParent[x];
	
	return parentOf[x][y] = calcParentOf(calcParentOf(x,y-1),y-1);
}

int lca(int x,int y)
{
	if (isParent(x,y)) return x;
	if (isParent(y,x)) return y;
	
	for (int i=maxh; i>=0; i--)
	{
		int tmp = calcParentOf(x,i);
		
		if (!isParent(tmp,y))
			x = tmp;
	}
	
	return directParent[x];
}

/**
 * Precondition: x is a proper ancestor of y
 */
int sideParent(int x,int y)
{
	for (int u : adj[x])
	{
		if (isParent(u,y))
			return u;
	}
	
	return -1;
}


main()
{
	ios_base::sync_with_stdio(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >> n;
	
	for (int i=1; i<=n-1; i++)
	{
		int x,y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	dfs(root);
	
	cin >> m;
	
	for (int i=1; i<=m; i++)
		cin >> a[i] >> b[i] >> c[i];
		
	memset(parentOf,-1,sizeof(parentOf));
	
	
	for (int i=1; i<=m; i++)
		pathWithTop[lca(a[i],b[i])].push_back(i);
	
	hld(root);
	
	for (int i=n; i>=1; i--)
	{
		int u = vertex[i];
		
		dp[u] = dpChildren[u]; // choose 0 path
		
		for (int p : pathWithTop[u])
		{
			int parentOfASide = sideParent(u,a[p]);
			int parentOfBSide = sideParent(u,b[p]);
			dp[u] = max(dp[u], getHLD(true,a[p],u)+getHLD(true,b[p],u)-dpChildren[u]-getHLD(false,a[p],parentOfASide)-getHLD(false,b[p],parentOfBSide) + c[p]);
		}
		
		update(false,u,dp[u]);
		if (u!=root)
		{
			update(true,directParent[u],dp[u]);
			dpChildren[directParent[u]]+=dp[u];
		}
	}
	
	cout << dp[1];
	
	return 0;
}

Compilation message (stderr)

election_campaign.cpp:184:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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