# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

111793 | 2019-05-16T07:36:14 Z | nxteru | Fireworks (APIO16_fireworks) | C++14 | 406 ms | 53004 KB |

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; #define F first #define S second #define PB push_back ll n,m,ans,vs[300005]; priority_queue<ll>p[300005]; vector<P>g[300005]; void up(int v,ll c){ if(p[v].size()==0){ p[v].push(c); p[v].push(c); }else{ ll x=p[v].top(); p[v].pop(); ll y=p[v].top(); p[v].pop(); p[v].push(x+c); p[v].push(y+c); } } void merge(int x,int y){ if(p[vs[x]].size()<p[vs[y]].size())swap(x,y); int py=y; y=vs[y]; x=vs[x]; vs[py]=x; while(!p[y].empty()){ p[x].push(p[y].top()); p[y].pop(); } } void dfs(int v){ ll s=g[v].size(); if(s==0)return; for(int i=0;i<g[v].size();i++){ ll u=g[v][i].F,c=g[v][i].S; dfs(u); up(vs[u],c); ans-=p[vs[u]].top(); merge(v,u); } for(int i=0;i<s-1;i++){ ans+=p[vs[v]].top(); p[vs[v]].pop(); } ans+=p[vs[v]].top(); } int main(void){ scanf("%lld%lld",&n,&m); n+=m; for(int i=0;i<n;i++)vs[i]=i; for(int i=1;i<n;i++){ ll q,c; scanf("%lld%lld",&q,&c); g[--q].PB(P(i,c)); } dfs(0); printf("%lld\n",ans); }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 16 ms | 16768 KB | Output is correct |

2 | Correct | 16 ms | 16768 KB | Output is correct |

3 | Correct | 16 ms | 16896 KB | Output is correct |

4 | Correct | 20 ms | 16740 KB | Output is correct |

5 | Correct | 16 ms | 16768 KB | Output is correct |

6 | Correct | 17 ms | 16768 KB | Output is correct |

7 | Correct | 12 ms | 16740 KB | Output is correct |

8 | Correct | 17 ms | 16768 KB | Output is correct |

9 | Correct | 18 ms | 16888 KB | Output is correct |

10 | Correct | 18 ms | 16768 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 16 ms | 16768 KB | Output is correct |

2 | Correct | 16 ms | 16768 KB | Output is correct |

3 | Correct | 17 ms | 16764 KB | Output is correct |

4 | Correct | 18 ms | 16768 KB | Output is correct |

5 | Correct | 15 ms | 16800 KB | Output is correct |

6 | Correct | 18 ms | 16768 KB | Output is correct |

7 | Correct | 16 ms | 16768 KB | Output is correct |

8 | Correct | 18 ms | 16768 KB | Output is correct |

9 | Correct | 15 ms | 16768 KB | Output is correct |

10 | Correct | 19 ms | 16768 KB | Output is correct |

11 | Correct | 15 ms | 16768 KB | Output is correct |

12 | Correct | 16 ms | 16768 KB | Output is correct |

13 | Correct | 16 ms | 16896 KB | Output is correct |

14 | Correct | 15 ms | 16768 KB | Output is correct |

15 | Correct | 16 ms | 16768 KB | Output is correct |

16 | Correct | 16 ms | 16768 KB | Output is correct |

17 | Correct | 16 ms | 16768 KB | Output is correct |

18 | Correct | 17 ms | 16768 KB | Output is correct |

19 | Correct | 16 ms | 16768 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 16 ms | 16768 KB | Output is correct |

2 | Correct | 16 ms | 16768 KB | Output is correct |

3 | Correct | 16 ms | 16896 KB | Output is correct |

4 | Correct | 20 ms | 16740 KB | Output is correct |

5 | Correct | 16 ms | 16768 KB | Output is correct |

6 | Correct | 17 ms | 16768 KB | Output is correct |

7 | Correct | 12 ms | 16740 KB | Output is correct |

8 | Correct | 17 ms | 16768 KB | Output is correct |

9 | Correct | 18 ms | 16888 KB | Output is correct |

10 | Correct | 18 ms | 16768 KB | Output is correct |

11 | Correct | 16 ms | 16768 KB | Output is correct |

12 | Correct | 16 ms | 16768 KB | Output is correct |

13 | Correct | 17 ms | 16764 KB | Output is correct |

14 | Correct | 18 ms | 16768 KB | Output is correct |

15 | Correct | 15 ms | 16800 KB | Output is correct |

16 | Correct | 18 ms | 16768 KB | Output is correct |

17 | Correct | 16 ms | 16768 KB | Output is correct |

18 | Correct | 18 ms | 16768 KB | Output is correct |

19 | Correct | 15 ms | 16768 KB | Output is correct |

20 | Correct | 19 ms | 16768 KB | Output is correct |

21 | Correct | 15 ms | 16768 KB | Output is correct |

22 | Correct | 16 ms | 16768 KB | Output is correct |

23 | Correct | 16 ms | 16896 KB | Output is correct |

24 | Correct | 15 ms | 16768 KB | Output is correct |

25 | Correct | 16 ms | 16768 KB | Output is correct |

26 | Correct | 16 ms | 16768 KB | Output is correct |

27 | Correct | 16 ms | 16768 KB | Output is correct |

28 | Correct | 17 ms | 16768 KB | Output is correct |

29 | Correct | 16 ms | 16768 KB | Output is correct |

30 | Correct | 17 ms | 16760 KB | Output is correct |

31 | Correct | 18 ms | 16896 KB | Output is correct |

32 | Correct | 19 ms | 16888 KB | Output is correct |

33 | Correct | 21 ms | 16896 KB | Output is correct |

34 | Correct | 18 ms | 17024 KB | Output is correct |

35 | Correct | 17 ms | 17024 KB | Output is correct |

36 | Correct | 17 ms | 17024 KB | Output is correct |

37 | Correct | 21 ms | 17152 KB | Output is correct |

38 | Correct | 18 ms | 17152 KB | Output is correct |

39 | Correct | 18 ms | 17152 KB | Output is correct |

40 | Correct | 17 ms | 17408 KB | Output is correct |

41 | Correct | 19 ms | 17452 KB | Output is correct |

42 | Correct | 19 ms | 17024 KB | Output is correct |

43 | Correct | 21 ms | 17280 KB | Output is correct |

44 | Correct | 22 ms | 17280 KB | Output is correct |

45 | Correct | 21 ms | 17280 KB | Output is correct |

46 | Correct | 18 ms | 17280 KB | Output is correct |

47 | Correct | 19 ms | 17408 KB | Output is correct |

48 | Correct | 18 ms | 17152 KB | Output is correct |

49 | Correct | 20 ms | 17280 KB | Output is correct |

50 | Correct | 22 ms | 17152 KB | Output is correct |

51 | Correct | 23 ms | 17144 KB | Output is correct |

52 | Correct | 32 ms | 17148 KB | Output is correct |

53 | Correct | 20 ms | 17280 KB | Output is correct |

54 | Correct | 22 ms | 17152 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 16 ms | 16768 KB | Output is correct |

2 | Correct | 16 ms | 16768 KB | Output is correct |

3 | Correct | 16 ms | 16896 KB | Output is correct |

4 | Correct | 20 ms | 16740 KB | Output is correct |

5 | Correct | 16 ms | 16768 KB | Output is correct |

6 | Correct | 17 ms | 16768 KB | Output is correct |

7 | Correct | 12 ms | 16740 KB | Output is correct |

8 | Correct | 17 ms | 16768 KB | Output is correct |

9 | Correct | 18 ms | 16888 KB | Output is correct |

10 | Correct | 18 ms | 16768 KB | Output is correct |

11 | Correct | 16 ms | 16768 KB | Output is correct |

12 | Correct | 16 ms | 16768 KB | Output is correct |

13 | Correct | 17 ms | 16764 KB | Output is correct |

14 | Correct | 18 ms | 16768 KB | Output is correct |

15 | Correct | 15 ms | 16800 KB | Output is correct |

16 | Correct | 18 ms | 16768 KB | Output is correct |

17 | Correct | 16 ms | 16768 KB | Output is correct |

18 | Correct | 18 ms | 16768 KB | Output is correct |

19 | Correct | 15 ms | 16768 KB | Output is correct |

20 | Correct | 19 ms | 16768 KB | Output is correct |

21 | Correct | 15 ms | 16768 KB | Output is correct |

22 | Correct | 16 ms | 16768 KB | Output is correct |

23 | Correct | 16 ms | 16896 KB | Output is correct |

24 | Correct | 15 ms | 16768 KB | Output is correct |

25 | Correct | 16 ms | 16768 KB | Output is correct |

26 | Correct | 16 ms | 16768 KB | Output is correct |

27 | Correct | 16 ms | 16768 KB | Output is correct |

28 | Correct | 17 ms | 16768 KB | Output is correct |

29 | Correct | 16 ms | 16768 KB | Output is correct |

30 | Correct | 17 ms | 16760 KB | Output is correct |

31 | Correct | 18 ms | 16896 KB | Output is correct |

32 | Correct | 19 ms | 16888 KB | Output is correct |

33 | Correct | 21 ms | 16896 KB | Output is correct |

34 | Correct | 18 ms | 17024 KB | Output is correct |

35 | Correct | 17 ms | 17024 KB | Output is correct |

36 | Correct | 17 ms | 17024 KB | Output is correct |

37 | Correct | 21 ms | 17152 KB | Output is correct |

38 | Correct | 18 ms | 17152 KB | Output is correct |

39 | Correct | 18 ms | 17152 KB | Output is correct |

40 | Correct | 17 ms | 17408 KB | Output is correct |

41 | Correct | 19 ms | 17452 KB | Output is correct |

42 | Correct | 19 ms | 17024 KB | Output is correct |

43 | Correct | 21 ms | 17280 KB | Output is correct |

44 | Correct | 22 ms | 17280 KB | Output is correct |

45 | Correct | 21 ms | 17280 KB | Output is correct |

46 | Correct | 18 ms | 17280 KB | Output is correct |

47 | Correct | 19 ms | 17408 KB | Output is correct |

48 | Correct | 18 ms | 17152 KB | Output is correct |

49 | Correct | 20 ms | 17280 KB | Output is correct |

50 | Correct | 22 ms | 17152 KB | Output is correct |

51 | Correct | 23 ms | 17144 KB | Output is correct |

52 | Correct | 32 ms | 17148 KB | Output is correct |

53 | Correct | 20 ms | 17280 KB | Output is correct |

54 | Correct | 22 ms | 17152 KB | Output is correct |

55 | Correct | 30 ms | 17792 KB | Output is correct |

56 | Correct | 76 ms | 20568 KB | Output is correct |

57 | Correct | 129 ms | 23032 KB | Output is correct |

58 | Correct | 150 ms | 24432 KB | Output is correct |

59 | Correct | 195 ms | 26676 KB | Output is correct |

60 | Correct | 247 ms | 28784 KB | Output is correct |

61 | Correct | 270 ms | 30656 KB | Output is correct |

62 | Correct | 321 ms | 31828 KB | Output is correct |

63 | Correct | 406 ms | 34424 KB | Output is correct |

64 | Correct | 361 ms | 35112 KB | Output is correct |

65 | Correct | 158 ms | 53004 KB | Output is correct |

66 | Correct | 158 ms | 52984 KB | Output is correct |

67 | Correct | 188 ms | 29620 KB | Output is correct |

68 | Correct | 246 ms | 45164 KB | Output is correct |

69 | Correct | 335 ms | 43684 KB | Output is correct |

70 | Correct | 318 ms | 43624 KB | Output is correct |

71 | Correct | 261 ms | 47840 KB | Output is correct |

72 | Correct | 256 ms | 48372 KB | Output is correct |

73 | Correct | 219 ms | 43744 KB | Output is correct |

74 | Correct | 223 ms | 44128 KB | Output is correct |

75 | Correct | 209 ms | 42468 KB | Output is correct |

76 | Correct | 215 ms | 42468 KB | Output is correct |

77 | Correct | 221 ms | 41768 KB | Output is correct |

78 | Correct | 257 ms | 39648 KB | Output is correct |

79 | Correct | 248 ms | 41956 KB | Output is correct |