Submission #78178

#	Time	Username	Problem	Language	Result	Execution time	Memory
78178		Pajaraja	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	486 ms	38284 KiB

election_campaign

#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 20
using namespace std;
vector<int> g[MAXN],a[MAXN],b[MAXN],c[MAXN];
int n,m,p[MAXL][MAXN],t,dp[MAXN],seg[8*MAXN],in[MAXN],out[MAXN];
void dfs(int s,int f)
{
	p[0][s]=f;
	in[s]=t++;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
	out[s]=t++;
}
void lca_init()
{
	dfs(1,1);
	for(int j=1;j<MAXL;j++) for(int i=1;i<=n;i++) p[j][i]=p[j-1][p[j-1][i]];
}
bool insub(int u,int v) {return in[u]>=in[v] && out[u]<=out[v];}
int lca(int u,int v)
{
	if(insub(u,v)) return v;
	if(insub(v,u)) return u;
	for(int j=MAXL-1;j>=0;j--) if(!insub(u,p[j][v])) v=p[j][v];
	return p[0][v];
}
void upd(int l,int r,int p,int v,int ind)
{
	if(l==r) {seg[ind]+=v; return;}
	int s=(l+r)/2;
	if(p<=s) upd(l,s,p,v,2*ind);
	else upd(s+1,r,p,v,2*ind+1);
	seg[ind]=seg[2*ind]+seg[2*ind+1];
}
int sum(int l,int r,int lt,int rt,int ind)
{
	if(lt<=l && rt>=r) return seg[ind];
	if(lt>r || l>rt) return 0;
	int s=(l+r)/2;
	return sum(l,s,lt,rt,2*ind)+sum(s+1,r,lt,rt,2*ind+1);
}
void dfssolve(int s,int f)
{
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfssolve(g[s][i],s);
	int x=sum(0,2*n,in[s],in[s],1);
	dp[s]=x;
	for(int i=0;i<a[s].size();i++) dp[s]=max(dp[s],c[s][i]+sum(0,2*n,in[s],in[a[s][i]],1)+sum(0,2*n,in[s],in[b[s][i]],1)-x);
	upd(0,2*n,in[f],dp[s],1);
	upd(0,2*n,in[s],-dp[s],1);
	upd(0,2*n,out[f],-dp[s],1);
	upd(0,2*n,out[s],dp[s],1);
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n-1;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		g[t1].push_back(t2);
		g[t2].push_back(t1);
	}
	lca_init();
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		int t1,t2,t3;
		scanf("%d%d%d",&t1,&t2,&t3);
		int x=lca(t1,t2);
		a[x].push_back(t1);
		b[x].push_back(t2);
		c[x].push_back(t3);
	}
	dfssolve(1,1);
	printf("%d",dp[1]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:11:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
              ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void dfssolve(int, int)':
election_campaign.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfssolve(g[s][i],s);
              ~^~~~~~~~~~~~
election_campaign.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[s].size();i++) dp[s]=max(dp[s],c[s][i]+sum(0,2*n,in[s],in[a[s][i]],1)+sum(0,2*n,in[s],in[b[s][i]],1)-x);
              ~^~~~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
election_campaign.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
   ~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
election_campaign.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t1,&t2,&t3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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