답안 #198628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198628	2020-01-27T02:10:48 Z	dennisstar	Fireworks (APIO16_fireworks)	C++17	100 / 100	351 ms	68740 KB

fireworks

#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int N, M;
vim adj[300010]; ll C[300010], D[300010];
priority_queue<ll> P[300010];

void Merge(int x, int y) {
	if (P[x].size()<P[y].size()) swap(P[x], P[y]);
	while (!P[y].empty()) { P[x].push(P[y].top()); P[y].pop(); }
}

void dfs(int now) {
	D[now]=C[now];
	if (now>N) {
		P[now].em(C[now]); P[now].em(C[now]);
		return ;
	}
	for (auto &i:adj[now]) {
		dfs(i); D[now]+=D[i];
		Merge(now, i);
	}
	for (int i=1; i<adj[now].size(); i++) P[now].pop();
	ll x = P[now].top(); P[now].pop();
	ll y = P[now].top(); P[now].pop();
	P[now].em(x+C[now]); P[now].em(y+C[now]);
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i=2; i<=N+M; i++) {
		int P; scanf("%d %lld", &P, &C[i]);
		adj[P].eb(i);
	}
	dfs(1); P[1].em(0);
	ll ans=D[1]; ll x=P[1].top(); P[1].pop();
	for (int i=0; !P[1].empty(); P[1].pop(), i++) {
		ans-=i*(x-P[1].top()); x=P[1].top();
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<adj[now].size(); i++) P[now].pop();
                ~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:43: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:45:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int P; scanf("%d %lld", &P, &C[i]);
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	16764 KB	Output is correct
2	Correct	15 ms	16760 KB	Output is correct
3	Correct	15 ms	16760 KB	Output is correct
4	Correct	15 ms	16760 KB	Output is correct
5	Correct	16 ms	16760 KB	Output is correct
6	Correct	16 ms	16760 KB	Output is correct
7	Correct	16 ms	16760 KB	Output is correct
8	Correct	15 ms	16760 KB	Output is correct
9	Correct	17 ms	16940 KB	Output is correct
10	Correct	16 ms	16760 KB	Output is correct

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	16888 KB	Output is correct
2	Correct	16 ms	16760 KB	Output is correct
3	Correct	18 ms	16888 KB	Output is correct
4	Correct	15 ms	16760 KB	Output is correct
5	Correct	16 ms	16760 KB	Output is correct
6	Correct	16 ms	16760 KB	Output is correct
7	Correct	15 ms	16760 KB	Output is correct
8	Correct	16 ms	16760 KB	Output is correct
9	Correct	16 ms	16760 KB	Output is correct
10	Correct	18 ms	16760 KB	Output is correct
11	Correct	16 ms	16760 KB	Output is correct
12	Correct	16 ms	16760 KB	Output is correct
13	Correct	15 ms	16760 KB	Output is correct
14	Correct	15 ms	16760 KB	Output is correct
15	Correct	15 ms	16760 KB	Output is correct
16	Correct	17 ms	16760 KB	Output is correct
17	Correct	15 ms	16760 KB	Output is correct
18	Correct	15 ms	16760 KB	Output is correct
19	Correct	16 ms	16764 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	16764 KB	Output is correct
2	Correct	15 ms	16760 KB	Output is correct
3	Correct	15 ms	16760 KB	Output is correct
4	Correct	15 ms	16760 KB	Output is correct
5	Correct	16 ms	16760 KB	Output is correct
6	Correct	16 ms	16760 KB	Output is correct
7	Correct	16 ms	16760 KB	Output is correct
8	Correct	15 ms	16760 KB	Output is correct
9	Correct	17 ms	16940 KB	Output is correct
10	Correct	16 ms	16760 KB	Output is correct
11	Correct	16 ms	16888 KB	Output is correct
12	Correct	16 ms	16760 KB	Output is correct
13	Correct	18 ms	16888 KB	Output is correct
14	Correct	15 ms	16760 KB	Output is correct
15	Correct	16 ms	16760 KB	Output is correct
16	Correct	16 ms	16760 KB	Output is correct
17	Correct	15 ms	16760 KB	Output is correct
18	Correct	16 ms	16760 KB	Output is correct
19	Correct	16 ms	16760 KB	Output is correct
20	Correct	18 ms	16760 KB	Output is correct
21	Correct	16 ms	16760 KB	Output is correct
22	Correct	16 ms	16760 KB	Output is correct
23	Correct	15 ms	16760 KB	Output is correct
24	Correct	15 ms	16760 KB	Output is correct
25	Correct	15 ms	16760 KB	Output is correct
26	Correct	17 ms	16760 KB	Output is correct
27	Correct	15 ms	16760 KB	Output is correct
28	Correct	15 ms	16760 KB	Output is correct
29	Correct	16 ms	16764 KB	Output is correct
30	Correct	15 ms	16760 KB	Output is correct
31	Correct	16 ms	16888 KB	Output is correct
32	Correct	16 ms	16888 KB	Output is correct
33	Correct	17 ms	17016 KB	Output is correct
34	Correct	17 ms	17016 KB	Output is correct
35	Correct	19 ms	17016 KB	Output is correct
36	Correct	19 ms	17144 KB	Output is correct
37	Correct	21 ms	17144 KB	Output is correct
38	Correct	18 ms	17144 KB	Output is correct
39	Correct	20 ms	17144 KB	Output is correct
40	Correct	18 ms	17656 KB	Output is correct
41	Correct	19 ms	17660 KB	Output is correct
42	Correct	17 ms	17020 KB	Output is correct
43	Correct	20 ms	17400 KB	Output is correct
44	Correct	20 ms	17400 KB	Output is correct
45	Correct	19 ms	17272 KB	Output is correct
46	Correct	19 ms	17272 KB	Output is correct
47	Correct	19 ms	17272 KB	Output is correct
48	Correct	21 ms	17144 KB	Output is correct
49	Correct	18 ms	17144 KB	Output is correct
50	Correct	18 ms	17144 KB	Output is correct
51	Correct	18 ms	17016 KB	Output is correct
52	Correct	20 ms	17144 KB	Output is correct
53	Correct	20 ms	17144 KB	Output is correct
54	Correct	19 ms	17144 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	16764 KB	Output is correct
2	Correct	15 ms	16760 KB	Output is correct
3	Correct	15 ms	16760 KB	Output is correct
4	Correct	15 ms	16760 KB	Output is correct
5	Correct	16 ms	16760 KB	Output is correct
6	Correct	16 ms	16760 KB	Output is correct
7	Correct	16 ms	16760 KB	Output is correct
8	Correct	15 ms	16760 KB	Output is correct
9	Correct	17 ms	16940 KB	Output is correct
10	Correct	16 ms	16760 KB	Output is correct
11	Correct	16 ms	16888 KB	Output is correct
12	Correct	16 ms	16760 KB	Output is correct
13	Correct	18 ms	16888 KB	Output is correct
14	Correct	15 ms	16760 KB	Output is correct
15	Correct	16 ms	16760 KB	Output is correct
16	Correct	16 ms	16760 KB	Output is correct
17	Correct	15 ms	16760 KB	Output is correct
18	Correct	16 ms	16760 KB	Output is correct
19	Correct	16 ms	16760 KB	Output is correct
20	Correct	18 ms	16760 KB	Output is correct
21	Correct	16 ms	16760 KB	Output is correct
22	Correct	16 ms	16760 KB	Output is correct
23	Correct	15 ms	16760 KB	Output is correct
24	Correct	15 ms	16760 KB	Output is correct
25	Correct	15 ms	16760 KB	Output is correct
26	Correct	17 ms	16760 KB	Output is correct
27	Correct	15 ms	16760 KB	Output is correct
28	Correct	15 ms	16760 KB	Output is correct
29	Correct	16 ms	16764 KB	Output is correct
30	Correct	15 ms	16760 KB	Output is correct
31	Correct	16 ms	16888 KB	Output is correct
32	Correct	16 ms	16888 KB	Output is correct
33	Correct	17 ms	17016 KB	Output is correct
34	Correct	17 ms	17016 KB	Output is correct
35	Correct	19 ms	17016 KB	Output is correct
36	Correct	19 ms	17144 KB	Output is correct
37	Correct	21 ms	17144 KB	Output is correct
38	Correct	18 ms	17144 KB	Output is correct
39	Correct	20 ms	17144 KB	Output is correct
40	Correct	18 ms	17656 KB	Output is correct
41	Correct	19 ms	17660 KB	Output is correct
42	Correct	17 ms	17020 KB	Output is correct
43	Correct	20 ms	17400 KB	Output is correct
44	Correct	20 ms	17400 KB	Output is correct
45	Correct	19 ms	17272 KB	Output is correct
46	Correct	19 ms	17272 KB	Output is correct
47	Correct	19 ms	17272 KB	Output is correct
48	Correct	21 ms	17144 KB	Output is correct
49	Correct	18 ms	17144 KB	Output is correct
50	Correct	18 ms	17144 KB	Output is correct
51	Correct	18 ms	17016 KB	Output is correct
52	Correct	20 ms	17144 KB	Output is correct
53	Correct	20 ms	17144 KB	Output is correct
54	Correct	19 ms	17144 KB	Output is correct
55	Correct	26 ms	17784 KB	Output is correct
56	Correct	61 ms	20600 KB	Output is correct
57	Correct	103 ms	23284 KB	Output is correct
58	Correct	145 ms	25328 KB	Output is correct
59	Correct	171 ms	28016 KB	Output is correct
60	Correct	217 ms	30836 KB	Output is correct
61	Correct	250 ms	33136 KB	Output is correct
62	Correct	287 ms	34544 KB	Output is correct
63	Correct	330 ms	37868 KB	Output is correct
64	Correct	351 ms	38900 KB	Output is correct
65	Correct	157 ms	68600 KB	Output is correct
66	Correct	156 ms	68740 KB	Output is correct
67	Correct	173 ms	35832 KB	Output is correct
68	Correct	237 ms	53548 KB	Output is correct
69	Correct	289 ms	50664 KB	Output is correct
70	Correct	299 ms	50544 KB	Output is correct
71	Correct	291 ms	48348 KB	Output is correct
72	Correct	291 ms	48612 KB	Output is correct
73	Correct	256 ms	44740 KB	Output is correct
74	Correct	260 ms	44900 KB	Output is correct
75	Correct	255 ms	43752 KB	Output is correct
76	Correct	261 ms	43744 KB	Output is correct
77	Correct	262 ms	43240 KB	Output is correct
78	Correct	266 ms	41672 KB	Output is correct
79	Correct	252 ms	42336 KB	Output is correct

답안 #198628

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