Submission #151969

#	Time	Username	Problem	Language	Result	Execution time	Memory
151969		TadijaSebez	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	401 ms	22984 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
vector<int> E[N];
int go[N][2],fa[N],sum[N],dp[N],sub[N];
void pull(int x){ sum[x]=sub[x]-dp[x]+sum[go[x][0]]+sum[go[x][1]];}
int pd(int x){ return go[fa[x]][0]==x?0:go[fa[x]][1]==x?1:-1;}
void rot(int x)
{
	assert(pd(x)!=-1);
	int y=fa[x],z=fa[y],p=pd(x),q=pd(y),w=go[x][p^1];
	if(~q) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
	if(w) fa[w]=y;fa[x]=z;fa[y]=x;
	pull(y);pull(x);
}
void splay(int x){ while(pd(x)!=-1){ if(pd(fa[x])!=-1) rot(pd(fa[x])==pd(x)?fa[x]:x);rot(x);}}
void access(int x){ for(splay(x),go[x][1]=0,pull(x);fa[x];rot(x)) splay(fa[x]),go[fa[x]][1]=x,pull(fa[x]);}
int get(int x, int y){ access(x);access(y);splay(x);return sum[x];}
int lca(int x, int y){ access(x);access(y);splay(x);return fa[x]?fa[x]:go[x][0]==y?y:x;}
int a[N],b[N],c[N];
vector<int> plan[N];
void DFS(int u, int p){ if(p) fa[u]=p;for(int v:E[u]) if(v!=p) DFS(v,u);}
void Solve(int u, int p)
{
	for(int v:E[u]) if(v!=p)
	{
		Solve(v,u);
		sub[u]+=dp[v];
	}
	dp[u]=sub[u];
	for(int i:plan[u])
	{
		int g=0;
		if(a[i]!=u) g+=get(a[i],u);
		if(b[i]!=u) g+=get(b[i],u);
		dp[u]=max(dp[u],sub[u]+g+c[i]);
	}
	pull(u);
}
int main()
{
	int n,m;
	scanf("%i",&n);
	for(int i=1,u,v;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	DFS(1,0);
	scanf("%i",&m);
	for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),plan[lca(a[i],b[i])].pb(i);
	Solve(1,0);
	printf("%i\n",dp[1]);
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void rot(int)':
election_campaign.cpp:13:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~q) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
  ^~
election_campaign.cpp:13:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(~q) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
                    ^~
election_campaign.cpp:14:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(w) fa[w]=y;fa[x]=z;fa[y]=x;
  ^~
election_campaign.cpp:14:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(w) fa[w]=y;fa[x]=z;fa[y]=x;
                ^~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
election_campaign.cpp:45:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1,u,v;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
election_campaign.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&m);
  ~~~~~^~~~~~~~~
election_campaign.cpp:48:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),plan[lca(a[i],b[i])].pb(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