Submission #223753

#	Time	Username	Problem	Language	Result	Execution time	Memory
223753		arnold518	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	287 ms	37216 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, Q;
vector<int> adj[MAXN+10];

int par[MAXN+10][25];
int dep[MAXN+10];
int L[MAXN+10], R[MAXN+10], cnt;

struct Query
{
	int u, v, w;
};
vector<Query> A[MAXN+10];

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	par[now][0]=bef;
	L[now]=++cnt;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
	}
	R[now]=cnt;
}

int lca(int x, int y)
{
	int i, j;
	if(dep[x]<dep[y]) swap(x, y);
	for(i=20; i>=0; i--) if(dep[par[x][i]]>=dep[y]) x=par[x][i];
	if(x==y) return x;
	for(i=20; i>=0; i--) if(par[x][i]!=par[y][i]) x=par[x][i], y=par[y][i];
	return par[x][0];
}

struct BIT
{
	int tree[MAXN+10];
	void update(int i, int v) { for(; i<=N; i+=(i&-i)) tree[i]+=v; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
	void update(int l, int r, int v) { update(l, v); update(r+1, -v); }
}seg;
int dp[MAXN+10];

void dfs2(int now, int bef)
{
	int i, j;	
	vector<int> chd;

	int sum=0;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now);
		chd.push_back(nxt);
		sum+=dp[nxt];
	}

	dp[now]=sum;

	for(auto nxt : chd) seg.update(L[nxt], R[nxt], -dp[nxt]);	
	for(auto &it : A[now])
	{
		int v=seg.query(L[it.u])+seg.query(L[it.v])+sum+it.w;
		dp[now]=max(dp[now], v);
	}
	seg.update(L[now], R[now], sum);
}

int main()
{
	int i, j;

	scanf("%d", &N);
	for(i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(1, 1, 1);
	for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	scanf("%d", &Q);
	while(Q--)
	{
		int u, v, w, k;
		scanf("%d%d%d", &u, &v, &k);
		w=lca(u, v);
		A[w].push_back({u, v, k});
	}

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

Compilation message (stderr)

election_campaign.cpp: In function 'int lca(int, int)':
election_campaign.cpp:38:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
election_campaign.cpp: In function 'void dfs2(int, int)':
election_campaign.cpp:57:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j; 
      ^
election_campaign.cpp:57:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j; 
         ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:88: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:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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