답안 #223750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223750	2020-04-16T09:51:23 Z	arnold518	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	202 ms	37116 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
{
	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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	4992 KB	Output is correct
3	Correct	8 ms	5376 KB	Output is correct
4	Correct	189 ms	36852 KB	Output is correct
5	Correct	177 ms	36856 KB	Output is correct
6	Correct	167 ms	36856 KB	Output is correct
7	Correct	171 ms	36856 KB	Output is correct
8	Correct	176 ms	36856 KB	Output is correct
9	Correct	164 ms	36856 KB	Output is correct
10	Correct	184 ms	36984 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	4992 KB	Output is correct
3	Correct	8 ms	5376 KB	Output is correct
4	Correct	189 ms	36852 KB	Output is correct
5	Correct	177 ms	36856 KB	Output is correct
6	Correct	167 ms	36856 KB	Output is correct
7	Correct	171 ms	36856 KB	Output is correct
8	Correct	176 ms	36856 KB	Output is correct
9	Correct	164 ms	36856 KB	Output is correct
10	Correct	184 ms	36984 KB	Output is correct
11	Correct	21 ms	6144 KB	Output is correct
12	Correct	179 ms	37112 KB	Output is correct
13	Correct	177 ms	37112 KB	Output is correct
14	Correct	165 ms	37112 KB	Output is correct
15	Correct	182 ms	37116 KB	Output is correct
16	Correct	166 ms	37112 KB	Output is correct
17	Correct	173 ms	37112 KB	Output is correct
18	Correct	174 ms	37112 KB	Output is correct
19	Correct	163 ms	37112 KB	Output is correct
20	Correct	178 ms	36984 KB	Output is correct