답안 #81647 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81647	2018-10-25T22:32:42 Z	Plurm	Fireworks (APIO16_fireworks)	C++11	100 / 100	767 ms	187348 KB

fireworks

#include <bits/stdc++.h>
using namespace std;
vector<int> g[300005];
multiset<long long> sack[300005];
int info[300005];
int c[300005];
long long slope[300005];
long long yint[300005];
int sz[300005];
void dfs(int u,int p = -1){
	sz[u] = 1;
	int mindex = -1;
	int mx = 0;
	for(int v : g[u]){
		if(v == p) continue;
		dfs(v,u);
		sz[u] += sz[v];
		if(sz[v] > mx){
			mx = sz[v];
			mindex = v;
		}
	}
	if(mindex == -1){
		info[u] = u;
		sack[u].insert(c[u]);
		sack[u].insert(c[u]);
		yint[u] = (long long)c[u];
		slope[u] = -1ll;
	}else{
		info[u] = info[mindex];
		for(int v : g[u]){
			if(v == p) continue;
			if(v == mindex) continue;
			for(long long x : sack[info[v]]){
				sack[info[u]].insert(x);
			}
			yint[info[u]] += yint[info[v]];
			slope[info[u]] += slope[info[v]];
		}
		long long opt = *sack[info[u]].rbegin();
		while(!sack[info[u]].empty() && slope[info[u]] + (long long)sack[info[u]].size() > 0ll){
			opt = *sack[info[u]].rbegin();
			sack[info[u]].erase(sack[info[u]].find(opt));
		}
		long long opt2 = *sack[info[u]].rbegin();
		sack[info[u]].erase(sack[info[u]].find(opt2));
		sack[info[u]].insert(opt + (long long)c[u]);
		sack[info[u]].insert(opt2 + (long long)c[u]);
		yint[info[u]] += (long long)c[u];
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 2; i <= n+m; i++){
		int p;
		scanf("%d%d",&p,c+i);
		g[i].push_back(p);
		g[p].push_back(i);
	}
	dfs(1);
	long long ly = yint[info[1]];
	long long ls = slope[info[1]];
	long long lp = 0ll;
	long long mn = ly;
	for(auto x : sack[info[1]]){
		ly += ls * (x - lp);
		ls++;
		lp = x;
		mn = min(mn,ly);
	}
	printf("%lld\n",mn);
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p,c+i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	21624 KB	Output is correct
2	Correct	21 ms	21684 KB	Output is correct
3	Correct	21 ms	21684 KB	Output is correct
4	Correct	20 ms	21684 KB	Output is correct
5	Correct	20 ms	21684 KB	Output is correct
6	Correct	20 ms	21684 KB	Output is correct
7	Correct	20 ms	21684 KB	Output is correct
8	Correct	21 ms	21684 KB	Output is correct
9	Correct	20 ms	21684 KB	Output is correct
10	Correct	20 ms	21684 KB	Output is correct

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	21684 KB	Output is correct
2	Correct	20 ms	21684 KB	Output is correct
3	Correct	20 ms	21704 KB	Output is correct
4	Correct	22 ms	21708 KB	Output is correct
5	Correct	20 ms	21764 KB	Output is correct
6	Correct	19 ms	21764 KB	Output is correct
7	Correct	20 ms	21764 KB	Output is correct
8	Correct	20 ms	21764 KB	Output is correct
9	Correct	20 ms	21764 KB	Output is correct
10	Correct	20 ms	21764 KB	Output is correct
11	Correct	20 ms	21764 KB	Output is correct
12	Correct	20 ms	21808 KB	Output is correct
13	Correct	21 ms	21812 KB	Output is correct
14	Correct	19 ms	21812 KB	Output is correct
15	Correct	20 ms	21812 KB	Output is correct
16	Correct	21 ms	21912 KB	Output is correct
17	Correct	21 ms	21912 KB	Output is correct
18	Correct	21 ms	21912 KB	Output is correct
19	Correct	20 ms	21912 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	21624 KB	Output is correct
2	Correct	21 ms	21684 KB	Output is correct
3	Correct	21 ms	21684 KB	Output is correct
4	Correct	20 ms	21684 KB	Output is correct
5	Correct	20 ms	21684 KB	Output is correct
6	Correct	20 ms	21684 KB	Output is correct
7	Correct	20 ms	21684 KB	Output is correct
8	Correct	21 ms	21684 KB	Output is correct
9	Correct	20 ms	21684 KB	Output is correct
10	Correct	20 ms	21684 KB	Output is correct
11	Correct	21 ms	21684 KB	Output is correct
12	Correct	20 ms	21684 KB	Output is correct
13	Correct	20 ms	21704 KB	Output is correct
14	Correct	22 ms	21708 KB	Output is correct
15	Correct	20 ms	21764 KB	Output is correct
16	Correct	19 ms	21764 KB	Output is correct
17	Correct	20 ms	21764 KB	Output is correct
18	Correct	20 ms	21764 KB	Output is correct
19	Correct	20 ms	21764 KB	Output is correct
20	Correct	20 ms	21764 KB	Output is correct
21	Correct	20 ms	21764 KB	Output is correct
22	Correct	20 ms	21808 KB	Output is correct
23	Correct	21 ms	21812 KB	Output is correct
24	Correct	19 ms	21812 KB	Output is correct
25	Correct	20 ms	21812 KB	Output is correct
26	Correct	21 ms	21912 KB	Output is correct
27	Correct	21 ms	21912 KB	Output is correct
28	Correct	21 ms	21912 KB	Output is correct
29	Correct	20 ms	21912 KB	Output is correct
30	Correct	20 ms	21912 KB	Output is correct
31	Correct	21 ms	21936 KB	Output is correct
32	Correct	21 ms	22096 KB	Output is correct
33	Correct	22 ms	22220 KB	Output is correct
34	Correct	22 ms	22308 KB	Output is correct
35	Correct	24 ms	22608 KB	Output is correct
36	Correct	28 ms	22692 KB	Output is correct
37	Correct	25 ms	22752 KB	Output is correct
38	Correct	25 ms	22948 KB	Output is correct
39	Correct	25 ms	23040 KB	Output is correct
40	Correct	24 ms	23112 KB	Output is correct
41	Correct	23 ms	23220 KB	Output is correct
42	Correct	24 ms	23220 KB	Output is correct
43	Correct	25 ms	23460 KB	Output is correct
44	Correct	25 ms	23532 KB	Output is correct
45	Correct	25 ms	23612 KB	Output is correct
46	Correct	26 ms	24188 KB	Output is correct
47	Correct	26 ms	24188 KB	Output is correct
48	Correct	26 ms	24188 KB	Output is correct
49	Correct	26 ms	24244 KB	Output is correct
50	Correct	25 ms	24244 KB	Output is correct
51	Correct	26 ms	24244 KB	Output is correct
52	Correct	25 ms	24244 KB	Output is correct
53	Correct	25 ms	24340 KB	Output is correct
54	Correct	26 ms	24532 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	21624 KB	Output is correct
2	Correct	21 ms	21684 KB	Output is correct
3	Correct	21 ms	21684 KB	Output is correct
4	Correct	20 ms	21684 KB	Output is correct
5	Correct	20 ms	21684 KB	Output is correct
6	Correct	20 ms	21684 KB	Output is correct
7	Correct	20 ms	21684 KB	Output is correct
8	Correct	21 ms	21684 KB	Output is correct
9	Correct	20 ms	21684 KB	Output is correct
10	Correct	20 ms	21684 KB	Output is correct
11	Correct	21 ms	21684 KB	Output is correct
12	Correct	20 ms	21684 KB	Output is correct
13	Correct	20 ms	21704 KB	Output is correct
14	Correct	22 ms	21708 KB	Output is correct
15	Correct	20 ms	21764 KB	Output is correct
16	Correct	19 ms	21764 KB	Output is correct
17	Correct	20 ms	21764 KB	Output is correct
18	Correct	20 ms	21764 KB	Output is correct
19	Correct	20 ms	21764 KB	Output is correct
20	Correct	20 ms	21764 KB	Output is correct
21	Correct	20 ms	21764 KB	Output is correct
22	Correct	20 ms	21808 KB	Output is correct
23	Correct	21 ms	21812 KB	Output is correct
24	Correct	19 ms	21812 KB	Output is correct
25	Correct	20 ms	21812 KB	Output is correct
26	Correct	21 ms	21912 KB	Output is correct
27	Correct	21 ms	21912 KB	Output is correct
28	Correct	21 ms	21912 KB	Output is correct
29	Correct	20 ms	21912 KB	Output is correct
30	Correct	20 ms	21912 KB	Output is correct
31	Correct	21 ms	21936 KB	Output is correct
32	Correct	21 ms	22096 KB	Output is correct
33	Correct	22 ms	22220 KB	Output is correct
34	Correct	22 ms	22308 KB	Output is correct
35	Correct	24 ms	22608 KB	Output is correct
36	Correct	28 ms	22692 KB	Output is correct
37	Correct	25 ms	22752 KB	Output is correct
38	Correct	25 ms	22948 KB	Output is correct
39	Correct	25 ms	23040 KB	Output is correct
40	Correct	24 ms	23112 KB	Output is correct
41	Correct	23 ms	23220 KB	Output is correct
42	Correct	24 ms	23220 KB	Output is correct
43	Correct	25 ms	23460 KB	Output is correct
44	Correct	25 ms	23532 KB	Output is correct
45	Correct	25 ms	23612 KB	Output is correct
46	Correct	26 ms	24188 KB	Output is correct
47	Correct	26 ms	24188 KB	Output is correct
48	Correct	26 ms	24188 KB	Output is correct
49	Correct	26 ms	24244 KB	Output is correct
50	Correct	25 ms	24244 KB	Output is correct
51	Correct	26 ms	24244 KB	Output is correct
52	Correct	25 ms	24244 KB	Output is correct
53	Correct	25 ms	24340 KB	Output is correct
54	Correct	26 ms	24532 KB	Output is correct
55	Correct	35 ms	25360 KB	Output is correct
56	Correct	89 ms	31312 KB	Output is correct
57	Correct	147 ms	37988 KB	Output is correct
58	Correct	214 ms	43456 KB	Output is correct
59	Correct	249 ms	50988 KB	Output is correct
60	Correct	316 ms	59224 KB	Output is correct
61	Correct	377 ms	66208 KB	Output is correct
62	Correct	424 ms	73508 KB	Output is correct
63	Correct	493 ms	85128 KB	Output is correct
64	Correct	537 ms	90260 KB	Output is correct
65	Correct	220 ms	98052 KB	Output is correct
66	Correct	235 ms	103124 KB	Output is correct
67	Correct	238 ms	103124 KB	Output is correct
68	Correct	407 ms	119740 KB	Output is correct
69	Correct	492 ms	122184 KB	Output is correct
70	Correct	493 ms	127068 KB	Output is correct
71	Correct	567 ms	168120 KB	Output is correct
72	Correct	555 ms	172480 KB	Output is correct
73	Correct	519 ms	172480 KB	Output is correct
74	Correct	517 ms	172480 KB	Output is correct
75	Correct	516 ms	172480 KB	Output is correct
76	Correct	521 ms	175720 KB	Output is correct
77	Correct	587 ms	176892 KB	Output is correct
78	Correct	646 ms	178372 KB	Output is correct
79	Correct	767 ms	187348 KB	Output is correct

답안 #81647

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 29.0 / 29.0

Subtask #4 45.0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
29.0 / 29.0

Subtask #4
45.0 / 45.0