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

623612 | 2022-08-06T05:42:14 Z | Arinoor | Subtree (INOI20_subtree) | C++17 | 74 ms | 21324 KB |

#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bug(x) cout << #x << " : " << x << '\n' #define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 10; const int mod = 1e9 + 7; const int inf = 1e9 + 10; int par[maxn], h[maxn], U[maxn]; int dp[maxn], val[maxn], val2[maxn], val3[maxn]; bool visited[maxn]; vector<int> G[maxn]; int add(int a, int b){ int c = a + b; if(c >= mod) c -= mod; if(c < 0) c += mod; return c; } int mul(int a, int b){ return 1ll * a * b % mod; } void dfs(int v){ visited[v] = true; for(int u : G[v]){ if(!visited[u]){ par[u] = v; h[u] = h[v] + 1; dfs(u); } else if(h[v] < h[u]){ U[v] = u; } } } void Dfs(int v){ for(int u : G[v]) if(par[u] == v) Dfs(u); if(!U[v]){ dp[v] = 1; for(int u : G[v]) if(par[u] == v) dp[v] = mul(dp[v], add(dp[u], 1)); return; } vector<int> V; V.pb(0); int u = U[v]; while(true){ V.pb(u); if(u == v) break; u = par[u]; } int m = V.size(); val[0] = 1; for(int i = 1; i < m; i ++){ val[i] = 1; int v = V[i]; for(int u : G[v]) if(par[u] == v and u != V[i - 1]) val[i] = mul(val[i], add(dp[u], 1)); } val2[0] = 1; for(int i = 1; i < m; i ++) val2[i] = mul(val2[i - 1], val[i]); val3[m - 1] = val[m - 1]; for(int i = m - 2; ~i; i --) val3[i] = mul(val3[i + 1], val[i]); for(int i = m - 2; ~i; i --) val3[i] = add(val3[i], val3[i + 1]); for(int i = 0; i < m - 2; i ++) dp[v] = add(dp[v], mul(val2[i], val3[i + 2])); } int main(){ ios; int n, m; cin >> n >> m; for(int i = 0; i < m; i ++){ int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); } dfs(1); Dfs(1); int ans = 0; for(int i = 1; i <= n; i ++){ ans = add(ans, dp[i]); } cout << ans << '\n'; }

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

1 | Correct | 2 ms | 2644 KB | Output is correct |

2 | Correct | 2 ms | 2684 KB | Output is correct |

3 | Correct | 2 ms | 2644 KB | Output is correct |

4 | Correct | 1 ms | 2644 KB | Output is correct |

5 | Correct | 2 ms | 2684 KB | Output is correct |

6 | Correct | 2 ms | 2644 KB | Output is correct |

7 | Correct | 2 ms | 2644 KB | Output is correct |

8 | Correct | 2 ms | 2644 KB | Output is correct |

9 | Correct | 2 ms | 2644 KB | Output is correct |

10 | Correct | 2 ms | 2644 KB | Output is correct |

11 | Correct | 2 ms | 2644 KB | Output is correct |

12 | Correct | 2 ms | 2644 KB | Output is correct |

13 | Correct | 2 ms | 2644 KB | Output is correct |

14 | Correct | 1 ms | 2684 KB | Output is correct |

15 | Correct | 2 ms | 2644 KB | Output is correct |

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

17 | Correct | 1 ms | 2644 KB | Output is correct |

18 | Correct | 2 ms | 2644 KB | Output is correct |

19 | Correct | 1 ms | 2684 KB | Output is correct |

20 | Correct | 2 ms | 2644 KB | Output is correct |

21 | Correct | 1 ms | 2688 KB | Output is correct |

22 | Correct | 1 ms | 2644 KB | Output is correct |

23 | Correct | 1 ms | 2644 KB | Output is correct |

24 | Correct | 2 ms | 2644 KB | Output is correct |

25 | Correct | 1 ms | 2688 KB | Output is correct |

26 | Correct | 1 ms | 2644 KB | Output is correct |

27 | Correct | 1 ms | 2644 KB | Output is correct |

28 | Correct | 1 ms | 2644 KB | Output is correct |

29 | Correct | 2 ms | 2684 KB | Output is correct |

30 | Correct | 2 ms | 2684 KB | Output is correct |

31 | Correct | 2 ms | 2644 KB | Output is correct |

32 | Correct | 1 ms | 2644 KB | Output is correct |

33 | Correct | 1 ms | 2644 KB | Output is correct |

34 | Correct | 2 ms | 2644 KB | Output is correct |

35 | Correct | 1 ms | 2644 KB | Output is correct |

36 | Correct | 2 ms | 2644 KB | Output is correct |

37 | Correct | 1 ms | 2644 KB | Output is correct |

38 | Correct | 1 ms | 2644 KB | Output is correct |

39 | Correct | 1 ms | 2644 KB | Output is correct |

40 | Correct | 2 ms | 2680 KB | Output is correct |

41 | Correct | 2 ms | 2644 KB | Output is correct |

42 | Correct | 2 ms | 2644 KB | Output is correct |

43 | Correct | 2 ms | 2772 KB | Output is correct |

44 | Correct | 2 ms | 2644 KB | Output is correct |

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

46 | Correct | 1 ms | 2644 KB | Output is correct |

47 | Correct | 2 ms | 2644 KB | Output is correct |

48 | Correct | 2 ms | 2644 KB | Output is correct |

49 | Correct | 2 ms | 2644 KB | Output is correct |

50 | Correct | 2 ms | 2644 KB | Output is correct |

51 | Correct | 2 ms | 2644 KB | Output is correct |

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

1 | Correct | 2 ms | 2688 KB | Output is correct |

2 | Correct | 5 ms | 3156 KB | Output is correct |

3 | Correct | 44 ms | 8360 KB | Output is correct |

4 | Correct | 42 ms | 8272 KB | Output is correct |

5 | Correct | 45 ms | 8328 KB | Output is correct |

6 | Correct | 43 ms | 8268 KB | Output is correct |

7 | Correct | 57 ms | 18384 KB | Output is correct |

8 | Correct | 60 ms | 14664 KB | Output is correct |

9 | Correct | 54 ms | 14584 KB | Output is correct |

10 | Correct | 35 ms | 8916 KB | Output is correct |

11 | Correct | 34 ms | 8424 KB | Output is correct |

12 | Correct | 54 ms | 8180 KB | Output is correct |

13 | Correct | 44 ms | 8224 KB | Output is correct |

14 | Correct | 42 ms | 12672 KB | Output is correct |

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

16 | Correct | 61 ms | 21324 KB | Output is correct |

17 | Correct | 43 ms | 8276 KB | Output is correct |

18 | Correct | 42 ms | 8252 KB | Output is correct |

19 | Correct | 46 ms | 8324 KB | Output is correct |

20 | Correct | 32 ms | 8516 KB | Output is correct |

21 | Correct | 32 ms | 8684 KB | Output is correct |

22 | Correct | 33 ms | 8644 KB | Output is correct |

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

1 | Correct | 2 ms | 2644 KB | Output is correct |

2 | Correct | 2 ms | 2684 KB | Output is correct |

3 | Correct | 2 ms | 2644 KB | Output is correct |

4 | Correct | 1 ms | 2644 KB | Output is correct |

5 | Correct | 2 ms | 2684 KB | Output is correct |

6 | Correct | 2 ms | 2644 KB | Output is correct |

7 | Correct | 2 ms | 2644 KB | Output is correct |

8 | Correct | 2 ms | 2644 KB | Output is correct |

9 | Correct | 2 ms | 2644 KB | Output is correct |

10 | Correct | 2 ms | 2644 KB | Output is correct |

11 | Correct | 2 ms | 2644 KB | Output is correct |

12 | Correct | 2 ms | 2644 KB | Output is correct |

13 | Correct | 2 ms | 2644 KB | Output is correct |

14 | Correct | 1 ms | 2684 KB | Output is correct |

15 | Correct | 2 ms | 2644 KB | Output is correct |

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

17 | Correct | 1 ms | 2644 KB | Output is correct |

18 | Correct | 2 ms | 2644 KB | Output is correct |

19 | Correct | 1 ms | 2684 KB | Output is correct |

20 | Correct | 2 ms | 2644 KB | Output is correct |

21 | Correct | 1 ms | 2688 KB | Output is correct |

22 | Correct | 1 ms | 2644 KB | Output is correct |

23 | Correct | 1 ms | 2644 KB | Output is correct |

24 | Correct | 2 ms | 2644 KB | Output is correct |

25 | Correct | 1 ms | 2688 KB | Output is correct |

26 | Correct | 1 ms | 2644 KB | Output is correct |

27 | Correct | 1 ms | 2644 KB | Output is correct |

28 | Correct | 1 ms | 2644 KB | Output is correct |

29 | Correct | 2 ms | 2684 KB | Output is correct |

30 | Correct | 2 ms | 2684 KB | Output is correct |

31 | Correct | 2 ms | 2644 KB | Output is correct |

32 | Correct | 1 ms | 2644 KB | Output is correct |

33 | Correct | 1 ms | 2644 KB | Output is correct |

34 | Correct | 2 ms | 2644 KB | Output is correct |

35 | Correct | 1 ms | 2644 KB | Output is correct |

36 | Correct | 2 ms | 2644 KB | Output is correct |

37 | Correct | 1 ms | 2644 KB | Output is correct |

38 | Correct | 1 ms | 2644 KB | Output is correct |

39 | Correct | 1 ms | 2644 KB | Output is correct |

40 | Correct | 2 ms | 2680 KB | Output is correct |

41 | Correct | 2 ms | 2644 KB | Output is correct |

42 | Correct | 2 ms | 2644 KB | Output is correct |

43 | Correct | 2 ms | 2772 KB | Output is correct |

44 | Correct | 2 ms | 2644 KB | Output is correct |

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

46 | Correct | 1 ms | 2644 KB | Output is correct |

47 | Correct | 2 ms | 2644 KB | Output is correct |

48 | Correct | 2 ms | 2644 KB | Output is correct |

49 | Correct | 2 ms | 2644 KB | Output is correct |

50 | Correct | 2 ms | 2644 KB | Output is correct |

51 | Correct | 2 ms | 2644 KB | Output is correct |

52 | Correct | 3 ms | 2900 KB | Output is correct |

53 | Correct | 4 ms | 2900 KB | Output is correct |

54 | Correct | 4 ms | 2900 KB | Output is correct |

55 | Correct | 3 ms | 3028 KB | Output is correct |

56 | Correct | 4 ms | 3468 KB | Output is correct |

57 | Correct | 3 ms | 2900 KB | Output is correct |

58 | Correct | 3 ms | 2900 KB | Output is correct |

59 | Correct | 3 ms | 3156 KB | Output is correct |

60 | Correct | 3 ms | 2900 KB | Output is correct |

61 | Correct | 3 ms | 2900 KB | Output is correct |

62 | Correct | 4 ms | 3028 KB | Output is correct |

63 | Correct | 3 ms | 2900 KB | Output is correct |

64 | Correct | 3 ms | 2900 KB | Output is correct |

65 | Correct | 3 ms | 2952 KB | Output is correct |

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

67 | Correct | 3 ms | 3028 KB | Output is correct |

68 | Correct | 4 ms | 3412 KB | Output is correct |

69 | Correct | 3 ms | 2900 KB | Output is correct |

70 | Correct | 3 ms | 2900 KB | Output is correct |

71 | Correct | 3 ms | 2900 KB | Output is correct |

72 | Correct | 4 ms | 2920 KB | Output is correct |

73 | Correct | 3 ms | 2952 KB | Output is correct |

74 | Correct | 4 ms | 2948 KB | Output is correct |

75 | Correct | 4 ms | 3216 KB | Output is correct |

76 | Correct | 3 ms | 3028 KB | Output is correct |

77 | Correct | 4 ms | 3464 KB | Output is correct |

78 | Correct | 3 ms | 3012 KB | Output is correct |

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

80 | Correct | 4 ms | 2952 KB | Output is correct |

81 | Correct | 3 ms | 3028 KB | Output is correct |

82 | Correct | 3 ms | 2956 KB | Output is correct |

83 | Correct | 3 ms | 3008 KB | Output is correct |

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

1 | Correct | 2 ms | 2644 KB | Output is correct |

2 | Correct | 2 ms | 2684 KB | Output is correct |

3 | Correct | 2 ms | 2644 KB | Output is correct |

4 | Correct | 1 ms | 2644 KB | Output is correct |

5 | Correct | 2 ms | 2684 KB | Output is correct |

6 | Correct | 2 ms | 2644 KB | Output is correct |

7 | Correct | 2 ms | 2644 KB | Output is correct |

8 | Correct | 2 ms | 2644 KB | Output is correct |

9 | Correct | 2 ms | 2644 KB | Output is correct |

10 | Correct | 2 ms | 2644 KB | Output is correct |

11 | Correct | 2 ms | 2644 KB | Output is correct |

12 | Correct | 2 ms | 2644 KB | Output is correct |

13 | Correct | 2 ms | 2644 KB | Output is correct |

14 | Correct | 1 ms | 2684 KB | Output is correct |

15 | Correct | 2 ms | 2644 KB | Output is correct |

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

17 | Correct | 1 ms | 2644 KB | Output is correct |

18 | Correct | 2 ms | 2644 KB | Output is correct |

19 | Correct | 1 ms | 2684 KB | Output is correct |

20 | Correct | 2 ms | 2644 KB | Output is correct |

21 | Correct | 1 ms | 2688 KB | Output is correct |

22 | Correct | 1 ms | 2644 KB | Output is correct |

23 | Correct | 1 ms | 2644 KB | Output is correct |

24 | Correct | 2 ms | 2644 KB | Output is correct |

25 | Correct | 1 ms | 2688 KB | Output is correct |

26 | Correct | 1 ms | 2644 KB | Output is correct |

27 | Correct | 1 ms | 2644 KB | Output is correct |

28 | Correct | 1 ms | 2644 KB | Output is correct |

29 | Correct | 2 ms | 2684 KB | Output is correct |

30 | Correct | 2 ms | 2684 KB | Output is correct |

31 | Correct | 2 ms | 2644 KB | Output is correct |

32 | Correct | 1 ms | 2644 KB | Output is correct |

33 | Correct | 1 ms | 2644 KB | Output is correct |

34 | Correct | 2 ms | 2644 KB | Output is correct |

35 | Correct | 1 ms | 2644 KB | Output is correct |

36 | Correct | 2 ms | 2644 KB | Output is correct |

37 | Correct | 1 ms | 2644 KB | Output is correct |

38 | Correct | 1 ms | 2644 KB | Output is correct |

39 | Correct | 1 ms | 2644 KB | Output is correct |

40 | Correct | 2 ms | 2680 KB | Output is correct |

41 | Correct | 2 ms | 2644 KB | Output is correct |

42 | Correct | 2 ms | 2644 KB | Output is correct |

43 | Correct | 2 ms | 2772 KB | Output is correct |

44 | Correct | 2 ms | 2644 KB | Output is correct |

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

46 | Correct | 1 ms | 2644 KB | Output is correct |

47 | Correct | 2 ms | 2644 KB | Output is correct |

48 | Correct | 2 ms | 2644 KB | Output is correct |

49 | Correct | 2 ms | 2644 KB | Output is correct |

50 | Correct | 2 ms | 2644 KB | Output is correct |

51 | Correct | 2 ms | 2644 KB | Output is correct |

52 | Correct | 2 ms | 2688 KB | Output is correct |

53 | Correct | 5 ms | 3156 KB | Output is correct |

54 | Correct | 44 ms | 8360 KB | Output is correct |

55 | Correct | 42 ms | 8272 KB | Output is correct |

56 | Correct | 45 ms | 8328 KB | Output is correct |

57 | Correct | 43 ms | 8268 KB | Output is correct |

58 | Correct | 57 ms | 18384 KB | Output is correct |

59 | Correct | 60 ms | 14664 KB | Output is correct |

60 | Correct | 54 ms | 14584 KB | Output is correct |

61 | Correct | 35 ms | 8916 KB | Output is correct |

62 | Correct | 34 ms | 8424 KB | Output is correct |

63 | Correct | 54 ms | 8180 KB | Output is correct |

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

65 | Correct | 42 ms | 12672 KB | Output is correct |

66 | Correct | 60 ms | 19888 KB | Output is correct |

67 | Correct | 61 ms | 21324 KB | Output is correct |

68 | Correct | 43 ms | 8276 KB | Output is correct |

69 | Correct | 42 ms | 8252 KB | Output is correct |

70 | Correct | 46 ms | 8324 KB | Output is correct |

71 | Correct | 32 ms | 8516 KB | Output is correct |

72 | Correct | 32 ms | 8684 KB | Output is correct |

73 | Correct | 33 ms | 8644 KB | Output is correct |

74 | Correct | 3 ms | 2900 KB | Output is correct |

75 | Correct | 4 ms | 2900 KB | Output is correct |

76 | Correct | 4 ms | 2900 KB | Output is correct |

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

78 | Correct | 4 ms | 3468 KB | Output is correct |

79 | Correct | 3 ms | 2900 KB | Output is correct |

80 | Correct | 3 ms | 2900 KB | Output is correct |

81 | Correct | 3 ms | 3156 KB | Output is correct |

82 | Correct | 3 ms | 2900 KB | Output is correct |

83 | Correct | 3 ms | 2900 KB | Output is correct |

84 | Correct | 4 ms | 3028 KB | Output is correct |

85 | Correct | 3 ms | 2900 KB | Output is correct |

86 | Correct | 3 ms | 2900 KB | Output is correct |

87 | Correct | 3 ms | 2952 KB | Output is correct |

88 | Correct | 4 ms | 2952 KB | Output is correct |

89 | Correct | 3 ms | 3028 KB | Output is correct |

90 | Correct | 4 ms | 3412 KB | Output is correct |

91 | Correct | 3 ms | 2900 KB | Output is correct |

92 | Correct | 3 ms | 2900 KB | Output is correct |

93 | Correct | 3 ms | 2900 KB | Output is correct |

94 | Correct | 4 ms | 2920 KB | Output is correct |

95 | Correct | 3 ms | 2952 KB | Output is correct |

96 | Correct | 4 ms | 2948 KB | Output is correct |

97 | Correct | 4 ms | 3216 KB | Output is correct |

98 | Correct | 3 ms | 3028 KB | Output is correct |

99 | Correct | 4 ms | 3464 KB | Output is correct |

100 | Correct | 3 ms | 3012 KB | Output is correct |

101 | Correct | 4 ms | 3336 KB | Output is correct |

102 | Correct | 4 ms | 2952 KB | Output is correct |

103 | Correct | 3 ms | 3028 KB | Output is correct |

104 | Correct | 3 ms | 2956 KB | Output is correct |

105 | Correct | 3 ms | 3008 KB | Output is correct |

106 | Correct | 49 ms | 8708 KB | Output is correct |

107 | Correct | 50 ms | 8764 KB | Output is correct |

108 | Correct | 50 ms | 8908 KB | Output is correct |

109 | Correct | 54 ms | 8824 KB | Output is correct |

110 | Correct | 36 ms | 8880 KB | Output is correct |

111 | Correct | 43 ms | 10312 KB | Output is correct |

112 | Correct | 68 ms | 16716 KB | Output is correct |

113 | Correct | 55 ms | 8780 KB | Output is correct |

114 | Correct | 55 ms | 8660 KB | Output is correct |

115 | Correct | 34 ms | 8604 KB | Output is correct |

116 | Correct | 62 ms | 17900 KB | Output is correct |

117 | Correct | 68 ms | 16504 KB | Output is correct |

118 | Correct | 33 ms | 10052 KB | Output is correct |

119 | Correct | 55 ms | 8716 KB | Output is correct |

120 | Correct | 56 ms | 8740 KB | Output is correct |

121 | Correct | 54 ms | 8780 KB | Output is correct |

122 | Correct | 55 ms | 8936 KB | Output is correct |

123 | Correct | 34 ms | 8772 KB | Output is correct |

124 | Correct | 33 ms | 8740 KB | Output is correct |

125 | Correct | 33 ms | 8564 KB | Output is correct |

126 | Correct | 45 ms | 8724 KB | Output is correct |

127 | Correct | 48 ms | 8768 KB | Output is correct |

128 | Correct | 45 ms | 8872 KB | Output is correct |

129 | Correct | 53 ms | 8908 KB | Output is correct |

130 | Correct | 34 ms | 8872 KB | Output is correct |

131 | Correct | 41 ms | 10316 KB | Output is correct |

132 | Correct | 74 ms | 16640 KB | Output is correct |

133 | Correct | 55 ms | 8780 KB | Output is correct |

134 | Correct | 56 ms | 8692 KB | Output is correct |

135 | Correct | 31 ms | 8524 KB | Output is correct |

136 | Correct | 69 ms | 15772 KB | Output is correct |

137 | Correct | 73 ms | 16080 KB | Output is correct |

138 | Correct | 35 ms | 9944 KB | Output is correct |

139 | Correct | 59 ms | 8720 KB | Output is correct |

140 | Correct | 59 ms | 8776 KB | Output is correct |

141 | Correct | 59 ms | 8908 KB | Output is correct |

142 | Correct | 63 ms | 8856 KB | Output is correct |

143 | Correct | 33 ms | 8764 KB | Output is correct |

144 | Correct | 35 ms | 8764 KB | Output is correct |

145 | Correct | 31 ms | 8576 KB | Output is correct |

146 | Correct | 55 ms | 8736 KB | Output is correct |

147 | Correct | 55 ms | 8752 KB | Output is correct |

148 | Correct | 54 ms | 9248 KB | Output is correct |

149 | Correct | 54 ms | 10348 KB | Output is correct |

150 | Correct | 72 ms | 19784 KB | Output is correct |

151 | Correct | 63 ms | 8852 KB | Output is correct |

152 | Correct | 68 ms | 9148 KB | Output is correct |

153 | Correct | 67 ms | 9252 KB | Output is correct |

154 | Correct | 52 ms | 10304 KB | Output is correct |

155 | Correct | 36 ms | 9096 KB | Output is correct |

156 | Correct | 65 ms | 17024 KB | Output is correct |

157 | Correct | 64 ms | 15876 KB | Output is correct |

158 | Correct | 63 ms | 14636 KB | Output is correct |

159 | Correct | 50 ms | 8580 KB | Output is correct |

160 | Correct | 71 ms | 17952 KB | Output is correct |

161 | Correct | 63 ms | 8620 KB | Output is correct |

162 | Correct | 41 ms | 8908 KB | Output is correct |