oj.uz

Submission #1046146

# Submission time Handle Problem Language Result Execution time Memory
1046146 2024-08-06T10:33:12 Z javotaz Subtree (INOI20_subtree) C++17
50 / 100
 2000 ms 33136 KB 
// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")
 
typedef long long ll;
 
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7, N = 1e5 + 12;
vector<int> g[N], e[N];
int n, m, tc, c[N], h[N];
ll ans, dp[N];
bool mrk[N];

void ip() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].pb(v), g[v].pb(u);
	}
}

pii dfs1(int u, int par = -1) {
	mrk[u] = true;
	pii res = {-1, n};
	for (auto i: g[u])
		if (i != par) {
			if (mrk[i]) { 
				if (!c[i])
					res = {++tc, h[i]};
			}
			else {
				h[i] = h[u] + 1;
				pii tmp = dfs1(i, u);
				if (tmp.S <= h[u])
					res = tmp;
			}
		}
	if (res.S > h[u]) 
		c[u] = ++tc;
	else
		c[u] = res.F;
	e[c[u]].pb(u);
	return res;
} 

void dfs(int u, int par = -1) {
	vector<ll> v;
	int sz = e[u].size(), t = -1;
	for (auto i: e[u]) {
		ll x = 1;
		for (auto j: g[i])
			if (c[j] != par && c[j] != u) {
				dfs(c[j], u);
				x = (x * (dp[c[j]] + 1)) % mod;
			}
			else if (c[j] == par)
				t = v.size();
		v.pb(x);
	}
	if (t != -1) {
		vector<ll> z(sz), p(sz);
		for (int i = t; i < sz; i++)
			z[i - t] = v[i];
		for (int i = 0; i < t; i++)
			z[sz - t + i] = v[i];
		p[0] = 1;
		for (int j = 1; j < sz - 1; ++j) {
			ll i = z[j];
			p[j] = (p[j - 1] * i) % mod;
		}
		for (int j = 1; j < sz - 1; ++j)
			p[j] = (p[j] + p[j - 1]) % mod;
		reverse(z.begin() + 1, z.end());
		ll x = 1;
		for (int j = 0; j < sz - 1; ++j) {
			ll i = z[j];
			x = (x * i) % mod;
			dp[u] = (dp[u] + x * p[sz - j - 2]) % mod;
		}
		if (sz == 1)
			dp[u] = z[0];
	}
	vector<ll> z(sz, 1);
	for (int i = 0; i < sz - 1; i++) 
		for (int j = 0; j < sz; ++j)
			z[j] = (z[j] * v[(j + i) % sz]) % mod, ans = (ans + z[j]) % mod;
	if (sz == 1)
		ans = (ans + v[0]) % mod;
}

void solve() {
	dfs1(0);
	dfs(1);
	cout << ans;
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6652 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6496 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6496 KB Output is correct
23 Correct 1 ms 6496 KB Output is correct
24 Correct 1 ms 6584 KB Output is correct
25 Correct 1 ms 6496 KB Output is correct
26 Correct 1 ms 6500 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6752 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6496 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6744 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6656 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Correct 1 ms 6492 KB Output is correct
44 Correct 1 ms 6492 KB Output is correct
45 Correct 2 ms 6492 KB Output is correct
46 Correct 1 ms 6492 KB Output is correct
47 Correct 1 ms 6648 KB Output is correct
48 Correct 1 ms 6492 KB Output is correct
49 Correct 1 ms 6492 KB Output is correct
50 Correct 1 ms 6492 KB Output is correct
51 Correct 1 ms 6492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 4 ms 7260 KB Output is correct
3 Correct 34 ms 13164 KB Output is correct
4 Correct 33 ms 12968 KB Output is correct
5 Correct 31 ms 13156 KB Output is correct
6 Correct 32 ms 13144 KB Output is correct
7 Correct 41 ms 27748 KB Output is correct
8 Correct 37 ms 22352 KB Output is correct
9 Correct 36 ms 22360 KB Output is correct
10 Correct 29 ms 13668 KB Output is correct
11 Correct 29 ms 13268 KB Output is correct
12 Correct 33 ms 12892 KB Output is correct
13 Correct 33 ms 13136 KB Output is correct
14 Correct 30 ms 19408 KB Output is correct
15 Correct 42 ms 31268 KB Output is correct
16 Correct 43 ms 33136 KB Output is correct
17 Correct 33 ms 13140 KB Output is correct
18 Correct 32 ms 13216 KB Output is correct
19 Correct 37 ms 13148 KB Output is correct
20 Correct 27 ms 13264 KB Output is correct
21 Correct 28 ms 13404 KB Output is correct
22 Correct 32 ms 13404 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6652 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6496 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6496 KB Output is correct
23 Correct 1 ms 6496 KB Output is correct
24 Correct 1 ms 6584 KB Output is correct
25 Correct 1 ms 6496 KB Output is correct
26 Correct 1 ms 6500 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6752 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6496 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6744 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6656 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Correct 1 ms 6492 KB Output is correct
44 Correct 1 ms 6492 KB Output is correct
45 Correct 2 ms 6492 KB Output is correct
46 Correct 1 ms 6492 KB Output is correct
47 Correct 1 ms 6648 KB Output is correct
48 Correct 1 ms 6492 KB Output is correct
49 Correct 1 ms 6492 KB Output is correct
50 Correct 1 ms 6492 KB Output is correct
51 Correct 1 ms 6492 KB Output is correct
52 Correct 2 ms 7000 KB Output is correct
53 Correct 2 ms 7004 KB Output is correct
54 Correct 3 ms 7004 KB Output is correct
55 Correct 2 ms 7004 KB Output is correct
56 Correct 2 ms 7308 KB Output is correct
57 Correct 2 ms 7004 KB Output is correct
58 Correct 2 ms 7044 KB Output is correct
59 Correct 3 ms 7004 KB Output is correct
60 Correct 2 ms 7004 KB Output is correct
61 Correct 2 ms 7004 KB Output is correct
62 Correct 2 ms 6844 KB Output is correct
63 Correct 2 ms 7004 KB Output is correct
64 Correct 2 ms 7000 KB Output is correct
65 Correct 3 ms 7004 KB Output is correct
66 Correct 3 ms 7004 KB Output is correct
67 Correct 2 ms 7004 KB Output is correct
68 Correct 2 ms 7004 KB Output is correct
69 Correct 2 ms 7004 KB Output is correct
70 Correct 2 ms 7004 KB Output is correct
71 Correct 2 ms 6984 KB Output is correct
72 Correct 2 ms 6748 KB Output is correct
73 Correct 2 ms 7084 KB Output is correct
74 Correct 2 ms 6748 KB Output is correct
75 Correct 2 ms 6932 KB Output is correct
76 Correct 2 ms 6748 KB Output is correct
77 Correct 2 ms 7260 KB Output is correct
78 Correct 8 ms 6996 KB Output is correct
79 Correct 9 ms 7004 KB Output is correct
80 Correct 3 ms 6748 KB Output is correct
81 Correct 3 ms 7004 KB Output is correct
82 Correct 4 ms 7004 KB Output is correct
83 Correct 3 ms 7004 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6652 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6496 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6496 KB Output is correct
23 Correct 1 ms 6496 KB Output is correct
24 Correct 1 ms 6584 KB Output is correct
25 Correct 1 ms 6496 KB Output is correct
26 Correct 1 ms 6500 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6752 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Correct 1 ms 6496 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 1 ms 6744 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6656 KB Output is correct
39 Correct 1 ms 6492 KB Output is correct
40 Correct 1 ms 6492 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Correct 1 ms 6492 KB Output is correct
44 Correct 1 ms 6492 KB Output is correct
45 Correct 2 ms 6492 KB Output is correct
46 Correct 1 ms 6492 KB Output is correct
47 Correct 1 ms 6648 KB Output is correct
48 Correct 1 ms 6492 KB Output is correct
49 Correct 1 ms 6492 KB Output is correct
50 Correct 1 ms 6492 KB Output is correct
51 Correct 1 ms 6492 KB Output is correct
52 Correct 1 ms 6492 KB Output is correct
53 Correct 4 ms 7260 KB Output is correct
54 Correct 34 ms 13164 KB Output is correct
55 Correct 33 ms 12968 KB Output is correct
56 Correct 31 ms 13156 KB Output is correct
57 Correct 32 ms 13144 KB Output is correct
58 Correct 41 ms 27748 KB Output is correct
59 Correct 37 ms 22352 KB Output is correct
60 Correct 36 ms 22360 KB Output is correct
61 Correct 29 ms 13668 KB Output is correct
62 Correct 29 ms 13268 KB Output is correct
63 Correct 33 ms 12892 KB Output is correct
64 Correct 33 ms 13136 KB Output is correct
65 Correct 30 ms 19408 KB Output is correct
66 Correct 42 ms 31268 KB Output is correct
67 Correct 43 ms 33136 KB Output is correct
68 Correct 33 ms 13140 KB Output is correct
69 Correct 32 ms 13216 KB Output is correct
70 Correct 37 ms 13148 KB Output is correct
71 Correct 27 ms 13264 KB Output is correct
72 Correct 28 ms 13404 KB Output is correct
73 Correct 32 ms 13404 KB Output is correct
74 Correct 2 ms 7000 KB Output is correct
75 Correct 2 ms 7004 KB Output is correct
76 Correct 3 ms 7004 KB Output is correct
77 Correct 2 ms 7004 KB Output is correct
78 Correct 2 ms 7308 KB Output is correct
79 Correct 2 ms 7004 KB Output is correct
80 Correct 2 ms 7044 KB Output is correct
81 Correct 3 ms 7004 KB Output is correct
82 Correct 2 ms 7004 KB Output is correct
83 Correct 2 ms 7004 KB Output is correct
84 Correct 2 ms 6844 KB Output is correct
85 Correct 2 ms 7004 KB Output is correct
86 Correct 2 ms 7000 KB Output is correct
87 Correct 3 ms 7004 KB Output is correct
88 Correct 3 ms 7004 KB Output is correct
89 Correct 2 ms 7004 KB Output is correct
90 Correct 2 ms 7004 KB Output is correct
91 Correct 2 ms 7004 KB Output is correct
92 Correct 2 ms 7004 KB Output is correct
93 Correct 2 ms 6984 KB Output is correct
94 Correct 2 ms 6748 KB Output is correct
95 Correct 2 ms 7084 KB Output is correct
96 Correct 2 ms 6748 KB Output is correct
97 Correct 2 ms 6932 KB Output is correct
98 Correct 2 ms 6748 KB Output is correct
99 Correct 2 ms 7260 KB Output is correct
100 Correct 8 ms 6996 KB Output is correct
101 Correct 9 ms 7004 KB Output is correct
102 Correct 3 ms 6748 KB Output is correct
103 Correct 3 ms 7004 KB Output is correct
104 Correct 4 ms 7004 KB Output is correct
105 Correct 3 ms 7004 KB Output is correct
106 Correct 32 ms 13904 KB Output is correct
107 Correct 33 ms 13784 KB Output is correct
108 Correct 35 ms 13660 KB Output is correct
109 Correct 45 ms 13612 KB Output is correct
110 Correct 31 ms 14768 KB Output is correct
111 Correct 36 ms 15268 KB Output is correct
112 Correct 38 ms 18952 KB Output is correct
113 Correct 41 ms 13076 KB Output is correct
114 Correct 33 ms 13344 KB Output is correct
115 Correct 28 ms 14540 KB Output is correct
116 Correct 47 ms 21840 KB Output is correct
117 Correct 40 ms 19548 KB Output is correct
118 Correct 28 ms 15184 KB Output is correct
119 Correct 42 ms 13044 KB Output is correct
120 Correct 45 ms 12884 KB Output is correct
121 Correct 43 ms 12632 KB Output is correct
122 Correct 48 ms 12728 KB Output is correct
123 Correct 34 ms 14580 KB Output is correct
124 Correct 35 ms 14712 KB Output is correct
125 Correct 32 ms 14556 KB Output is correct
126 Correct 38 ms 13916 KB Output is correct
127 Correct 39 ms 13920 KB Output is correct
128 Correct 46 ms 13816 KB Output is correct
129 Correct 38 ms 13544 KB Output is correct
130 Correct 40 ms 14676 KB Output is correct
131 Correct 36 ms 15232 KB Output is correct
132 Correct 48 ms 18660 KB Output is correct
133 Correct 39 ms 12892 KB Output is correct
134 Correct 39 ms 13288 KB Output is correct
135 Correct 29 ms 14364 KB Output is correct
136 Correct 43 ms 19520 KB Output is correct
137 Correct 51 ms 19236 KB Output is correct
138 Correct 31 ms 15152 KB Output is correct
139 Correct 41 ms 13048 KB Output is correct
140 Correct 35 ms 12836 KB Output is correct
141 Correct 46 ms 12580 KB Output is correct
142 Correct 45 ms 12488 KB Output is correct
143 Correct 43 ms 14692 KB Output is correct
144 Correct 33 ms 14492 KB Output is correct
145 Correct 31 ms 14532 KB Output is correct
146 Correct 41 ms 12020 KB Output is correct
147 Correct 53 ms 11764 KB Output is correct
148 Correct 307 ms 12072 KB Output is correct
149 Execution timed out 2091 ms 13184 KB Time limit exceeded
150 Halted 0 ms 0 KB -