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

723070 | 2023-04-13T08:16:22 Z | loctildore | Bi-ing Lottery Treekets (CCO22_day2problem1) | C++14 | 257 ms | 129100 KB |

#include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #define endl '\n' #define all(x) begin(x), end(x) #define MOD 1000000007 int n, k; int sz[4069]; int balls[4069]; int lft[4069], rht[4069], dir[4069]; ll perm[4069][4069]; bool done[4069][4069]; ll dp[4069][4069]; int calsz(int x) { if (!x) return 0; return sz[x] = calsz(lft[x]) + calsz(rht[x]) + 1 - balls[x]; } ll fnd(int x, int carry) { if (x == 0) return carry == 0; if (done[x][carry]) return dp[x][carry]; done[x][carry] = true; if (carry > sz[x]) return dp[x][carry] = 0; if (carry == sz[x]) { ll tmp = (fnd(lft[x], sz[lft[x]]) * fnd(rht[x], sz[rht[x]])) % MOD; tmp = (tmp * perm[carry + balls[x]][balls[x]]) % MOD; return dp[x][carry] = tmp; } if (dir[x] && balls[x] + carry >= sz[rht[x]]) { ll tmp = (fnd(lft[x], balls[x] + carry - sz[rht[x]]) * fnd(rht[x], sz[rht[x]])) % MOD; tmp = (tmp * perm[carry + balls[x]][balls[x]]) % MOD; dp[x][carry] = (dp[x][carry] + tmp) % MOD; } if (!dir[x] && balls[x] + carry >= sz[lft[x]]) { ll tmp = (fnd(lft[x], sz[lft[x]]) * fnd(rht[x], balls[x] + carry - sz[lft[x]])) % MOD; tmp = (tmp * perm[carry + balls[x]][balls[x]]) % MOD; dp[x][carry] = (dp[x][carry] + tmp) % MOD; } for (int i = 0; i <= balls[x]; i++) { ll tmp; if (dir[x]) { if (sz[rht[x]] <= carry + i) continue; tmp = (fnd(lft[x], balls[x] - i) * fnd(rht[x], carry + i)) % MOD; } else { if (sz[lft[x]] <= carry + i) continue; tmp = (fnd(lft[x], carry + i) * fnd(rht[x], balls[x] - i)) % MOD; } tmp = (tmp * perm[balls[x]][balls[x] - i]) % MOD; tmp = (tmp * perm[carry + i][i]) % MOD; dp[x][carry] = (dp[x][carry] + tmp) % MOD; } //cout<<x<<' '<<carry<<'?'<<sz[x]<<':'<<dp[x][carry]<<endl; return dp[x][carry]; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin>>n>>k; for (int i = 0; i < 4069; i++) { perm[i][0] = 1; for (int j = 1; j <= i; j++) { perm[i][j] = (perm[i-1][j-1] * i) % MOD; } } for (int i = 0; i < k; i++) { int a; cin>>a; balls[a]++; } for (int i = 1; i <= n; i++) { cin>>lft[i]>>rht[i]; dir[rht[i]] = true; } calsz(1); cout<<fnd(1, 0)<<endl; return 0; }

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

1 | Correct | 45 ms | 80460 KB | Output is correct |

2 | Correct | 46 ms | 80484 KB | Output is correct |

3 | Correct | 49 ms | 80476 KB | Output is correct |

4 | Correct | 46 ms | 80400 KB | Output is correct |

5 | Correct | 44 ms | 80588 KB | Output is correct |

6 | Correct | 44 ms | 80588 KB | Output is correct |

7 | Correct | 43 ms | 80556 KB | Output is correct |

8 | Correct | 46 ms | 80512 KB | Output is correct |

9 | Correct | 56 ms | 80588 KB | Output is correct |

10 | Correct | 43 ms | 80588 KB | Output is correct |

11 | Correct | 44 ms | 80464 KB | Output is correct |

12 | Correct | 51 ms | 80504 KB | Output is correct |

13 | Correct | 52 ms | 80564 KB | Output is correct |

14 | Correct | 52 ms | 80596 KB | Output is correct |

15 | Correct | 57 ms | 80492 KB | Output is correct |

16 | Correct | 46 ms | 80480 KB | Output is correct |

17 | Correct | 45 ms | 80588 KB | Output is correct |

18 | Correct | 57 ms | 80476 KB | Output is correct |

19 | Correct | 52 ms | 80524 KB | Output is correct |

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

1 | Correct | 76 ms | 113072 KB | Output is correct |

2 | Correct | 257 ms | 128128 KB | Output is correct |

3 | Correct | 47 ms | 80640 KB | Output is correct |

4 | Correct | 79 ms | 113092 KB | Output is correct |

5 | Correct | 79 ms | 113156 KB | Output is correct |

6 | Correct | 72 ms | 113160 KB | Output is correct |

7 | Correct | 136 ms | 121712 KB | Output is correct |

8 | Correct | 86 ms | 114720 KB | Output is correct |

9 | Correct | 116 ms | 119752 KB | Output is correct |

10 | Correct | 80 ms | 115916 KB | Output is correct |

11 | Correct | 183 ms | 126812 KB | Output is correct |

12 | Correct | 56 ms | 80588 KB | Output is correct |

13 | Correct | 156 ms | 118700 KB | Output is correct |

14 | Correct | 214 ms | 123696 KB | Output is correct |

15 | Correct | 60 ms | 80728 KB | Output is correct |

16 | Correct | 73 ms | 112704 KB | Output is correct |

17 | Correct | 147 ms | 117700 KB | Output is correct |

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

1 | Correct | 68 ms | 112672 KB | Output is correct |

2 | Correct | 61 ms | 113048 KB | Output is correct |

3 | Correct | 77 ms | 112664 KB | Output is correct |

4 | Correct | 66 ms | 112664 KB | Output is correct |

5 | Correct | 83 ms | 112728 KB | Output is correct |

6 | Correct | 66 ms | 112732 KB | Output is correct |

7 | Correct | 72 ms | 112640 KB | Output is correct |

8 | Correct | 64 ms | 112728 KB | Output is correct |

9 | Correct | 67 ms | 112720 KB | Output is correct |

10 | Correct | 76 ms | 112788 KB | Output is correct |

11 | Correct | 66 ms | 112656 KB | Output is correct |

12 | Correct | 66 ms | 113240 KB | Output is correct |

13 | Correct | 57 ms | 112868 KB | Output is correct |

14 | Correct | 76 ms | 112640 KB | Output is correct |

15 | Correct | 66 ms | 112644 KB | Output is correct |

16 | Correct | 74 ms | 112684 KB | Output is correct |

17 | Correct | 64 ms | 112688 KB | Output is correct |

18 | Correct | 61 ms | 112796 KB | Output is correct |

19 | Correct | 65 ms | 112788 KB | Output is correct |

20 | Correct | 75 ms | 96504 KB | Output is correct |

21 | Correct | 72 ms | 111052 KB | Output is correct |

22 | Correct | 63 ms | 112472 KB | Output is correct |

23 | Correct | 73 ms | 111840 KB | Output is correct |

24 | Correct | 71 ms | 112592 KB | Output is correct |

25 | Correct | 70 ms | 109344 KB | Output is correct |

26 | Correct | 83 ms | 112476 KB | Output is correct |

27 | Correct | 73 ms | 111148 KB | Output is correct |

28 | Correct | 66 ms | 112132 KB | Output is correct |

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

1 | Correct | 45 ms | 80460 KB | Output is correct |

2 | Correct | 46 ms | 80484 KB | Output is correct |

3 | Correct | 49 ms | 80476 KB | Output is correct |

4 | Correct | 46 ms | 80400 KB | Output is correct |

5 | Correct | 44 ms | 80588 KB | Output is correct |

6 | Correct | 44 ms | 80588 KB | Output is correct |

7 | Correct | 43 ms | 80556 KB | Output is correct |

8 | Correct | 46 ms | 80512 KB | Output is correct |

9 | Correct | 56 ms | 80588 KB | Output is correct |

10 | Correct | 43 ms | 80588 KB | Output is correct |

11 | Correct | 44 ms | 80464 KB | Output is correct |

12 | Correct | 51 ms | 80504 KB | Output is correct |

13 | Correct | 52 ms | 80564 KB | Output is correct |

14 | Correct | 52 ms | 80596 KB | Output is correct |

15 | Correct | 57 ms | 80492 KB | Output is correct |

16 | Correct | 46 ms | 80480 KB | Output is correct |

17 | Correct | 45 ms | 80588 KB | Output is correct |

18 | Correct | 57 ms | 80476 KB | Output is correct |

19 | Correct | 52 ms | 80524 KB | Output is correct |

20 | Correct | 76 ms | 113072 KB | Output is correct |

21 | Correct | 257 ms | 128128 KB | Output is correct |

22 | Correct | 47 ms | 80640 KB | Output is correct |

23 | Correct | 79 ms | 113092 KB | Output is correct |

24 | Correct | 79 ms | 113156 KB | Output is correct |

25 | Correct | 72 ms | 113160 KB | Output is correct |

26 | Correct | 136 ms | 121712 KB | Output is correct |

27 | Correct | 86 ms | 114720 KB | Output is correct |

28 | Correct | 116 ms | 119752 KB | Output is correct |

29 | Correct | 80 ms | 115916 KB | Output is correct |

30 | Correct | 183 ms | 126812 KB | Output is correct |

31 | Correct | 56 ms | 80588 KB | Output is correct |

32 | Correct | 156 ms | 118700 KB | Output is correct |

33 | Correct | 214 ms | 123696 KB | Output is correct |

34 | Correct | 60 ms | 80728 KB | Output is correct |

35 | Correct | 73 ms | 112704 KB | Output is correct |

36 | Correct | 147 ms | 117700 KB | Output is correct |

37 | Correct | 68 ms | 112672 KB | Output is correct |

38 | Correct | 61 ms | 113048 KB | Output is correct |

39 | Correct | 77 ms | 112664 KB | Output is correct |

40 | Correct | 66 ms | 112664 KB | Output is correct |

41 | Correct | 83 ms | 112728 KB | Output is correct |

42 | Correct | 66 ms | 112732 KB | Output is correct |

43 | Correct | 72 ms | 112640 KB | Output is correct |

44 | Correct | 64 ms | 112728 KB | Output is correct |

45 | Correct | 67 ms | 112720 KB | Output is correct |

46 | Correct | 76 ms | 112788 KB | Output is correct |

47 | Correct | 66 ms | 112656 KB | Output is correct |

48 | Correct | 66 ms | 113240 KB | Output is correct |

49 | Correct | 57 ms | 112868 KB | Output is correct |

50 | Correct | 76 ms | 112640 KB | Output is correct |

51 | Correct | 66 ms | 112644 KB | Output is correct |

52 | Correct | 74 ms | 112684 KB | Output is correct |

53 | Correct | 64 ms | 112688 KB | Output is correct |

54 | Correct | 61 ms | 112796 KB | Output is correct |

55 | Correct | 65 ms | 112788 KB | Output is correct |

56 | Correct | 75 ms | 96504 KB | Output is correct |

57 | Correct | 72 ms | 111052 KB | Output is correct |

58 | Correct | 63 ms | 112472 KB | Output is correct |

59 | Correct | 73 ms | 111840 KB | Output is correct |

60 | Correct | 71 ms | 112592 KB | Output is correct |

61 | Correct | 70 ms | 109344 KB | Output is correct |

62 | Correct | 83 ms | 112476 KB | Output is correct |

63 | Correct | 73 ms | 111148 KB | Output is correct |

64 | Correct | 66 ms | 112132 KB | Output is correct |

65 | Correct | 78 ms | 109540 KB | Output is correct |

66 | Correct | 76 ms | 112704 KB | Output is correct |

67 | Correct | 82 ms | 110412 KB | Output is correct |

68 | Correct | 64 ms | 112652 KB | Output is correct |

69 | Correct | 87 ms | 113024 KB | Output is correct |

70 | Correct | 68 ms | 112988 KB | Output is correct |

71 | Correct | 67 ms | 112876 KB | Output is correct |

72 | Correct | 88 ms | 112988 KB | Output is correct |

73 | Correct | 63 ms | 112704 KB | Output is correct |

74 | Correct | 60 ms | 112764 KB | Output is correct |

75 | Correct | 78 ms | 112736 KB | Output is correct |

76 | Correct | 67 ms | 110528 KB | Output is correct |

77 | Correct | 59 ms | 110584 KB | Output is correct |

78 | Correct | 61 ms | 113044 KB | Output is correct |

79 | Correct | 230 ms | 129100 KB | Output is correct |

80 | Correct | 66 ms | 113076 KB | Output is correct |

81 | Correct | 76 ms | 110568 KB | Output is correct |

82 | Correct | 61 ms | 112780 KB | Output is correct |

83 | Correct | 64 ms | 112768 KB | Output is correct |

84 | Correct | 64 ms | 80476 KB | Output is correct |

85 | Correct | 80 ms | 112720 KB | Output is correct |

86 | Correct | 71 ms | 112724 KB | Output is correct |

87 | Correct | 83 ms | 112684 KB | Output is correct |

88 | Correct | 80 ms | 112680 KB | Output is correct |

89 | Correct | 71 ms | 112724 KB | Output is correct |

90 | Correct | 76 ms | 112700 KB | Output is correct |

91 | Correct | 67 ms | 112740 KB | Output is correct |

92 | Correct | 61 ms | 112784 KB | Output is correct |

93 | Correct | 76 ms | 112788 KB | Output is correct |

94 | Correct | 74 ms | 113612 KB | Output is correct |

95 | Correct | 78 ms | 113656 KB | Output is correct |

96 | Correct | 64 ms | 112696 KB | Output is correct |

97 | Correct | 70 ms | 112716 KB | Output is correct |

98 | Correct | 80 ms | 112728 KB | Output is correct |

99 | Correct | 75 ms | 112672 KB | Output is correct |

100 | Correct | 66 ms | 112772 KB | Output is correct |

101 | Correct | 73 ms | 112816 KB | Output is correct |

102 | Correct | 59 ms | 99680 KB | Output is correct |

103 | Correct | 70 ms | 110576 KB | Output is correct |

104 | Correct | 67 ms | 111368 KB | Output is correct |