Submission #223751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223751	2020-04-16T09:52:13 Z	arnold518	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	195 ms	35064 KB

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
{
	ll tree[MAXN+10];
	void update(int i, ll v) { for(; i<=N; i+=(i&-i)) tree[i]+=v; }
	ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
	void update(int l, int r, ll 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

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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4992 KB	Output is correct
2	Incorrect	7 ms	4992 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4992 KB	Output is correct
2	Correct	7 ms	4992 KB	Output is correct
3	Correct	8 ms	5376 KB	Output is correct
4	Correct	180 ms	34936 KB	Output is correct
5	Correct	165 ms	34936 KB	Output is correct
6	Correct	158 ms	34944 KB	Output is correct
7	Correct	166 ms	34936 KB	Output is correct
8	Correct	166 ms	34936 KB	Output is correct
9	Correct	160 ms	34936 KB	Output is correct
10	Correct	172 ms	34936 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4992 KB	Output is correct
2	Correct	7 ms	4992 KB	Output is correct
3	Correct	8 ms	5376 KB	Output is correct
4	Correct	180 ms	34936 KB	Output is correct
5	Correct	165 ms	34936 KB	Output is correct
6	Correct	158 ms	34944 KB	Output is correct
7	Correct	166 ms	34936 KB	Output is correct
8	Correct	166 ms	34936 KB	Output is correct
9	Correct	160 ms	34936 KB	Output is correct
10	Correct	172 ms	34936 KB	Output is correct
11	Correct	21 ms	5888 KB	Output is correct
12	Correct	176 ms	34936 KB	Output is correct
13	Correct	175 ms	35064 KB	Output is correct
14	Correct	159 ms	34936 KB	Output is correct
15	Correct	189 ms	35064 KB	Output is correct
16	Correct	165 ms	34936 KB	Output is correct
17	Correct	170 ms	34940 KB	Output is correct
18	Correct	169 ms	34936 KB	Output is correct
19	Correct	160 ms	34936 KB	Output is correct
20	Correct	171 ms	34936 KB	Output is correct