oj.uz

Submission #660027

# Submission time Handle Problem Language Result Execution time Memory
660027 2022-11-20T08:58:50 Z highway_to_hell Star Trek (CEOI20_startrek) C++14
50 / 100
 1000 ms 80336 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
	return a;
}
int mul(int a, int b) {
	return 1ll*a*b%mod;
}
int pw(int a, ll b) {
	int out = 1;
	while (b) {
		if (b&1) out = mul(out, a);
		a = mul(a,a);
		b>>=1;
	}
	return out;
}

const int N = 1e5 + 50, LG = 60;
int n;
ll d;
vector<int> adj[N];
pii dpdw[N], dpup[N], dp[LG][N][2], out[N][2], tmp[N][2]; 

void dfs(int u, int p) {
	int cnt, sum, sbd;
	cnt = sum = sbd = 0;
	for (int v:adj[u]) {
		if(v == p) continue;
		dfs(v, u);
		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;
	}
	dpdw[u].F = !cnt;
	if (cnt >= 2) return;
	dpdw[u].S = (cnt? sbd:sum+1);
}

void sfd(int u, int p) {
	int cnt, sum, sbd;
	cnt = dpup[u].F;
	sum = dpup[u].S;
	sbd = dpup[u].F*dpup[u].S;
	for (int v:adj[u]) {
		if (v == p) continue;
		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;
	}
	for (int v:adj[u]) {
		if (v == p) continue;
		sum = add(sum, -dpdw[v].S);
		sbd = add(sbd, -dpdw[v].F*dpdw[v].S);
		cnt -= dpdw[v].F;
		
		dpup[v].F = !cnt;
		if (cnt < 2) dpup[v].S = (cnt? sbd:sum+1);

		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;

		sfd(v, u);
	}
}

void solve() {
	cin >> n >> d;
	for (int i = 1; i <= n-1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	sfd(1, 0);
	for (int u = 1; u <= n; u++) {
		if (dpdw[u].F) {
			dp[0][u][dpup[u].F^1] = {1, (dpup[u].F? dpup[u].S : add(dpdw[u].S, dpup[u].S))};
		}
		else {
			dp[0][u][0] = {1, (dpup[u].F ? 0 : dpdw[u].S)};
		}
	}
	for (int k = 1; k < LG; k++) {
		int sum = 0;
		int sa = 0, sb = 0;
		for (int u = 1; u <= n; u++) {
			sum = add(sum, dp[k-1][u][1].F);
			sa = add(sa, dp[k-1][u][0].S);
			sb = add(sb, dp[k-1][u][1].S);
		}
		for (int u = 1; u <= n; u++) {
			dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][0].F, pw(mul(n, n), 1ll<<(k-1))));
			dp[k][u][0].F = add(dp[k][u][0].F, -mul(dp[k-1][u][0].S, sum));
			dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][1].S, sum));
			dp[k][u][0].S = add(mul(dp[k-1][u][0].S, sa), mul(dp[k-1][u][1].S, sb));

			dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][1].F, pw(mul(n, n), 1ll<<(k-1))));
			dp[k][u][1].F = add(dp[k][u][1].F, -mul(dp[k-1][u][1].S, sum));
			dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][0].S, sum));
			dp[k][u][1].S = add(mul(dp[k-1][u][1].S, sa), mul(dp[k-1][u][0].S, sb));
		}
	}

	bool flg = 0;
	d++;
	for (int k = 0; k < LG; k++) {
		if (!(d>>k&1)) continue;
		if (!flg) {
			for (int u = 1; u <= n; u++) {
				out[u][0] = dp[k][u][0];
				out[u][1] = dp[k][u][1];
			}
			flg = 1;
			continue;
		}
		int sum = 0;
		int sa = 0, sb = 0;
		for (int u = 1; u <= n; u++) {
			sum = add(sum, dp[k][u][1].F);
			sa = add(sa, dp[k][u][0].S);
			sb = add(sb, dp[k][u][1].S);
		}
		for (int u = 1; u <= n; u++) {
			tmp[u][0] = tmp[u][1] = {0, 0};

			tmp[u][0].F = add(tmp[u][0].F, mul(out[u][0].F, pw(mul(n, n), 1ll<<k)));
			tmp[u][0].F = add(tmp[u][0].F, -mul(out[u][0].S, sum));
			tmp[u][0].F = add(tmp[u][0].F, mul(out[u][1].S, sum));
			tmp[u][0].S = add(mul(out[u][0].S, sa), mul(out[u][1].S, sb));

			tmp[u][1].F = add(tmp[u][1].F, mul(out[u][1].F, pw(mul(n, n), 1ll<<k)));
			tmp[u][1].F = add(tmp[u][1].F, -mul(out[u][1].S, sum));
			tmp[u][1].F = add(tmp[u][1].F, mul(out[u][0].S, sum));
			tmp[u][1].S = add(mul(out[u][1].S, sa), mul(out[u][0].S, sb));

			out[u][0] = tmp[u][0];
			out[u][1] = tmp[u][1];
		}
	}
	cout << out[1][0].F << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 20 ms 4048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3064 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 4 ms 3156 KB Output is correct
4 Correct 5 ms 3188 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3064 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 4 ms 3156 KB Output is correct
4 Correct 5 ms 3188 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct
7 Correct 21 ms 4180 KB Output is correct
8 Correct 19 ms 4140 KB Output is correct
9 Correct 19 ms 4052 KB Output is correct
10 Correct 22 ms 4084 KB Output is correct
11 Correct 20 ms 4024 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3064 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 4 ms 3156 KB Output is correct
4 Correct 5 ms 3188 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct
7 Correct 21 ms 4180 KB Output is correct
8 Correct 19 ms 4140 KB Output is correct
9 Correct 19 ms 4052 KB Output is correct
10 Correct 22 ms 4084 KB Output is correct
11 Correct 20 ms 4024 KB Output is correct
12 Execution timed out 1095 ms 80336 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3064 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 4 ms 3156 KB Output is correct
4 Correct 5 ms 3188 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct
7 Correct 21 ms 4180 KB Output is correct
8 Correct 19 ms 4140 KB Output is correct
9 Correct 19 ms 4052 KB Output is correct
10 Correct 22 ms 4084 KB Output is correct
11 Correct 20 ms 4024 KB Output is correct
12 Correct 2 ms 3028 KB Output is correct
13 Correct 20 ms 4140 KB Output is correct
14 Correct 2 ms 3028 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 4 ms 3192 KB Output is correct
17 Correct 4 ms 3192 KB Output is correct
18 Correct 4 ms 3184 KB Output is correct
19 Correct 4 ms 3184 KB Output is correct
20 Correct 4 ms 3100 KB Output is correct
21 Correct 22 ms 4156 KB Output is correct
22 Correct 19 ms 4140 KB Output is correct
23 Correct 19 ms 4048 KB Output is correct
24 Correct 20 ms 4028 KB Output is correct
25 Correct 20 ms 4092 KB Output is correct
26 Correct 21 ms 4108 KB Output is correct
27 Correct 21 ms 4212 KB Output is correct
28 Correct 18 ms 3816 KB Output is correct
29 Correct 21 ms 4104 KB Output is correct
30 Correct 20 ms 4052 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3064 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 4 ms 3156 KB Output is correct
4 Correct 5 ms 3188 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct
7 Correct 21 ms 4180 KB Output is correct
8 Correct 19 ms 4140 KB Output is correct
9 Correct 19 ms 4052 KB Output is correct
10 Correct 22 ms 4084 KB Output is correct
11 Correct 20 ms 4024 KB Output is correct
12 Execution timed out 1095 ms 80336 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 20 ms 4048 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 3 ms 3064 KB Output is correct
9 Correct 4 ms 3156 KB Output is correct
10 Correct 4 ms 3156 KB Output is correct
11 Correct 5 ms 3188 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 21 ms 4180 KB Output is correct
15 Correct 19 ms 4140 KB Output is correct
16 Correct 19 ms 4052 KB Output is correct
17 Correct 22 ms 4084 KB Output is correct
18 Correct 20 ms 4024 KB Output is correct
19 Execution timed out 1095 ms 80336 KB Time limit exceeded
20 Halted 0 ms 0 KB -