답안 #54635 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54635	2018-07-04T09:56:14 Z	ikura355	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	451 ms	152572 KB

election_campaign

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

const int maxn = 1e5 + 5;
const int mlog = 17;

int n,m;
vector<int> way[maxn];
vector<tuple<int,int,int>> have[maxn];

int cur, st[maxn], ft[maxn];

int h[maxn], par[maxn][20];

int tree[maxn*4];

int dp[maxn];

void dfs(int u, int last) {
	st[u] = ++cur;

	h[u] = h[last] + 1;
	par[u][0] = last;
	for(int i=1;i<=mlog;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto v : way[u]) {
		if(v==last) continue;
		dfs(v,u);
	}

	ft[u] = cur;
}

int lca(int u, int v) {
	if(h[u]<h[v]) swap(u,v);
	for(int i=mlog;i>=0;i--) if(h[par[u][i]]>=h[v]) u = par[u][i];
	if(u==v) return u;
	for(int i=mlog;i>=0;i--) {
		if(par[u][i]!=par[v][i]) {
			u = par[u][i]; v = par[v][i];
		}
	}
	return par[u][0];
}

void update(int pos, int l, int r, int x, int y, int val) {
	if(l>r || r<x || y<l) return ;
	if(x<=l && r<=y) {
		tree[pos] += val;
		return ;
	}
	int mid = (l+r)/2;
	update(pos<<1,l,mid,x,y,val); update(pos<<1|1,mid+1,r,x,y,val);
}

int query(int pos, int l, int r, int x) {
	if(l>r || r<x || x<l) return 0;
	if(l==r) return tree[pos];
	int mid = (l+r)/2;
	return tree[pos] + query(pos<<1,l,mid,x) + query(pos<<1|1,mid+1,r,x);
}

void solve(int u, int last) {
	int sum = 0;
	//solve child
	for(auto v : way[u]) {
		if(v==last) continue;
		solve(v, u);
		sum += dp[v];
	}
	//solve u
	dp[u] = sum;
	for(auto t : have[u]) {
		int x,y,val;
		tie(x,y,val) = t;
		int change = query(1,1,n,st[x]) + query(1,1,n,st[y]);
		dp[u] = max(dp[u], sum + val + change);
	}
	//update subtree u
	update(1,1,n,st[u],ft[u],-dp[u]+sum);
}

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

	dfs(1,0);

	scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		int u,v,val; scanf("%d%d%d",&u,&v,&val);
		have[lca(u,v)].emplace_back(u,v,val);
	}

	solve(1,0);

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

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
election_campaign.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
election_campaign.cpp:93:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v,val; scanf("%d%d%d",&u,&v,&val);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4988 KB	Output is correct
2	Correct	6 ms	5104 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	8 ms	5380 KB	Output is correct
5	Correct	148 ms	20176 KB	Output is correct
6	Correct	80 ms	29044 KB	Output is correct
7	Correct	142 ms	29044 KB	Output is correct
8	Correct	115 ms	29044 KB	Output is correct
9	Correct	199 ms	29044 KB	Output is correct
10	Correct	123 ms	29044 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	29044 KB	Output is correct
2	Correct	6 ms	29044 KB	Output is correct
3	Correct	7 ms	29044 KB	Output is correct
4	Correct	259 ms	38296 KB	Output is correct
5	Correct	269 ms	40592 KB	Output is correct
6	Correct	217 ms	43200 KB	Output is correct
7	Correct	248 ms	45652 KB	Output is correct
8	Correct	217 ms	48016 KB	Output is correct
9	Correct	208 ms	50596 KB	Output is correct
10	Correct	267 ms	53064 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	29044 KB	Output is correct
2	Correct	6 ms	29044 KB	Output is correct
3	Correct	7 ms	29044 KB	Output is correct
4	Correct	259 ms	38296 KB	Output is correct
5	Correct	269 ms	40592 KB	Output is correct
6	Correct	217 ms	43200 KB	Output is correct
7	Correct	248 ms	45652 KB	Output is correct
8	Correct	217 ms	48016 KB	Output is correct
9	Correct	208 ms	50596 KB	Output is correct
10	Correct	267 ms	53064 KB	Output is correct
11	Correct	24 ms	53064 KB	Output is correct
12	Correct	224 ms	56088 KB	Output is correct
13	Correct	221 ms	58840 KB	Output is correct
14	Correct	207 ms	61508 KB	Output is correct
15	Correct	231 ms	64212 KB	Output is correct
16	Correct	205 ms	66984 KB	Output is correct
17	Correct	228 ms	69672 KB	Output is correct
18	Correct	218 ms	72532 KB	Output is correct
19	Correct	209 ms	75296 KB	Output is correct
20	Correct	212 ms	78056 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	251 ms	78056 KB	Output is correct
2	Correct	215 ms	82860 KB	Output is correct
3	Correct	371 ms	82860 KB	Output is correct
4	Correct	213 ms	82860 KB	Output is correct
5	Correct	329 ms	86644 KB	Output is correct
6	Correct	251 ms	86644 KB	Output is correct
7	Correct	375 ms	91396 KB	Output is correct
8	Correct	269 ms	91396 KB	Output is correct
9	Correct	249 ms	100256 KB	Output is correct
10	Correct	451 ms	100256 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4988 KB	Output is correct
2	Correct	6 ms	5104 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	8 ms	5380 KB	Output is correct
5	Correct	148 ms	20176 KB	Output is correct
6	Correct	80 ms	29044 KB	Output is correct
7	Correct	142 ms	29044 KB	Output is correct
8	Correct	115 ms	29044 KB	Output is correct
9	Correct	199 ms	29044 KB	Output is correct
10	Correct	123 ms	29044 KB	Output is correct
11	Correct	7 ms	100256 KB	Output is correct
12	Correct	9 ms	100256 KB	Output is correct
13	Correct	8 ms	100256 KB	Output is correct
14	Correct	8 ms	100256 KB	Output is correct
15	Correct	7 ms	100256 KB	Output is correct
16	Correct	9 ms	100256 KB	Output is correct
17	Correct	7 ms	100256 KB	Output is correct
18	Correct	8 ms	100256 KB	Output is correct
19	Correct	7 ms	100256 KB	Output is correct
20	Correct	7 ms	100256 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4988 KB	Output is correct
2	Correct	6 ms	5104 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	8 ms	5380 KB	Output is correct
5	Correct	148 ms	20176 KB	Output is correct
6	Correct	80 ms	29044 KB	Output is correct
7	Correct	142 ms	29044 KB	Output is correct
8	Correct	115 ms	29044 KB	Output is correct
9	Correct	199 ms	29044 KB	Output is correct
10	Correct	123 ms	29044 KB	Output is correct
11	Correct	8 ms	29044 KB	Output is correct
12	Correct	6 ms	29044 KB	Output is correct
13	Correct	7 ms	29044 KB	Output is correct
14	Correct	259 ms	38296 KB	Output is correct
15	Correct	269 ms	40592 KB	Output is correct
16	Correct	217 ms	43200 KB	Output is correct
17	Correct	248 ms	45652 KB	Output is correct
18	Correct	217 ms	48016 KB	Output is correct
19	Correct	208 ms	50596 KB	Output is correct
20	Correct	267 ms	53064 KB	Output is correct
21	Correct	24 ms	53064 KB	Output is correct
22	Correct	224 ms	56088 KB	Output is correct
23	Correct	221 ms	58840 KB	Output is correct
24	Correct	207 ms	61508 KB	Output is correct
25	Correct	231 ms	64212 KB	Output is correct
26	Correct	205 ms	66984 KB	Output is correct
27	Correct	228 ms	69672 KB	Output is correct
28	Correct	218 ms	72532 KB	Output is correct
29	Correct	209 ms	75296 KB	Output is correct
30	Correct	212 ms	78056 KB	Output is correct
31	Correct	251 ms	78056 KB	Output is correct
32	Correct	215 ms	82860 KB	Output is correct
33	Correct	371 ms	82860 KB	Output is correct
34	Correct	213 ms	82860 KB	Output is correct
35	Correct	329 ms	86644 KB	Output is correct
36	Correct	251 ms	86644 KB	Output is correct
37	Correct	375 ms	91396 KB	Output is correct
38	Correct	269 ms	91396 KB	Output is correct
39	Correct	249 ms	100256 KB	Output is correct
40	Correct	451 ms	100256 KB	Output is correct
41	Correct	7 ms	100256 KB	Output is correct
42	Correct	9 ms	100256 KB	Output is correct
43	Correct	8 ms	100256 KB	Output is correct
44	Correct	8 ms	100256 KB	Output is correct
45	Correct	7 ms	100256 KB	Output is correct
46	Correct	9 ms	100256 KB	Output is correct
47	Correct	7 ms	100256 KB	Output is correct
48	Correct	8 ms	100256 KB	Output is correct
49	Correct	7 ms	100256 KB	Output is correct
50	Correct	7 ms	100256 KB	Output is correct
51	Correct	346 ms	100256 KB	Output is correct
52	Correct	309 ms	108432 KB	Output is correct
53	Correct	371 ms	108432 KB	Output is correct
54	Correct	216 ms	108432 KB	Output is correct
55	Correct	286 ms	108468 KB	Output is correct
56	Correct	305 ms	119396 KB	Output is correct
57	Correct	394 ms	119396 KB	Output is correct
58	Correct	221 ms	119396 KB	Output is correct
59	Correct	358 ms	119724 KB	Output is correct
60	Correct	261 ms	130484 KB	Output is correct
61	Correct	343 ms	130484 KB	Output is correct
62	Correct	291 ms	130484 KB	Output is correct
63	Correct	355 ms	130484 KB	Output is correct
64	Correct	245 ms	141424 KB	Output is correct
65	Correct	352 ms	141424 KB	Output is correct
66	Correct	230 ms	141424 KB	Output is correct
67	Correct	268 ms	141460 KB	Output is correct
68	Correct	228 ms	152572 KB	Output is correct
69	Correct	331 ms	152572 KB	Output is correct
70	Correct	230 ms	152572 KB	Output is correct

답안 #54635

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 30.0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
30.0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
40.0 / 40.0