oj.uz

Submission #660080

# Submission time Handle Problem Language Result Execution time Memory
660080 2022-11-20T10:20:43 Z Kahou Star Trek (CEOI20_startrek) C++14
100 / 100
 532 ms 117036 KB 
#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;
}

const int N = 1e5 + 50, LG = 62;
int n, pw[LG];
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;
        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);
        }
        pw[0] = mul(n, n);
        for (int k = 1; k < LG; k++) {
                pw[k] = mul(pw[k-1], pw[k-1]);
        }

        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[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[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;
        for (int k = 0; k < LG; k++) {
                if (!(d&(1ll<<k))) 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[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[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 5 ms 4072 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 2 ms 3028 KB Output is correct
3 Correct 2 ms 3104 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 1 ms 3028 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 5 ms 4176 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 4 ms 4052 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 5 ms 4052 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 5 ms 4176 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 4 ms 4052 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 5 ms 4052 KB Output is correct
12 Correct 394 ms 110436 KB Output is correct
13 Correct 242 ms 115404 KB Output is correct
14 Correct 249 ms 106216 KB Output is correct
15 Correct 331 ms 106088 KB Output is correct
16 Correct 291 ms 105984 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 5 ms 4176 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 4 ms 4052 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 5 ms 4052 KB Output is correct
12 Correct 2 ms 3028 KB Output is correct
13 Correct 5 ms 4180 KB Output is correct
14 Correct 2 ms 3028 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 2 ms 3156 KB Output is correct
18 Correct 2 ms 3156 KB Output is correct
19 Correct 3 ms 3264 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 5 ms 4180 KB Output is correct
22 Correct 4 ms 4180 KB Output is correct
23 Correct 4 ms 4052 KB Output is correct
24 Correct 5 ms 4052 KB Output is correct
25 Correct 4 ms 4052 KB Output is correct
26 Correct 5 ms 4180 KB Output is correct
27 Correct 4 ms 4180 KB Output is correct
28 Correct 4 ms 3848 KB Output is correct
29 Correct 5 ms 4180 KB Output is correct
30 Correct 4 ms 4180 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 5 ms 4176 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 4 ms 4052 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 5 ms 4052 KB Output is correct
12 Correct 394 ms 110436 KB Output is correct
13 Correct 242 ms 115404 KB Output is correct
14 Correct 249 ms 106216 KB Output is correct
15 Correct 331 ms 106088 KB Output is correct
16 Correct 291 ms 105984 KB Output is correct
17 Correct 2 ms 3028 KB Output is correct
18 Correct 5 ms 4180 KB Output is correct
19 Correct 2 ms 3028 KB Output is correct
20 Correct 2 ms 3028 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 2 ms 3156 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 3 ms 3264 KB Output is correct
25 Correct 2 ms 3156 KB Output is correct
26 Correct 5 ms 4180 KB Output is correct
27 Correct 4 ms 4180 KB Output is correct
28 Correct 4 ms 4052 KB Output is correct
29 Correct 5 ms 4052 KB Output is correct
30 Correct 4 ms 4052 KB Output is correct
31 Correct 5 ms 4180 KB Output is correct
32 Correct 4 ms 4180 KB Output is correct
33 Correct 4 ms 3848 KB Output is correct
34 Correct 5 ms 4180 KB Output is correct
35 Correct 4 ms 4180 KB Output is correct
36 Correct 395 ms 110384 KB Output is correct
37 Correct 257 ms 115368 KB Output is correct
38 Correct 237 ms 106124 KB Output is correct
39 Correct 332 ms 106112 KB Output is correct
40 Correct 292 ms 106124 KB Output is correct
41 Correct 446 ms 114712 KB Output is correct
42 Correct 240 ms 107212 KB Output is correct
43 Correct 225 ms 95952 KB Output is correct
44 Correct 359 ms 107600 KB Output is correct
45 Correct 287 ms 107656 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 5 ms 4072 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3104 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 1 ms 3028 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 5 ms 4176 KB Output is correct
15 Correct 4 ms 4180 KB Output is correct
16 Correct 4 ms 4052 KB Output is correct
17 Correct 5 ms 4052 KB Output is correct
18 Correct 5 ms 4052 KB Output is correct
19 Correct 394 ms 110436 KB Output is correct
20 Correct 242 ms 115404 KB Output is correct
21 Correct 249 ms 106216 KB Output is correct
22 Correct 331 ms 106088 KB Output is correct
23 Correct 291 ms 105984 KB Output is correct
24 Correct 2 ms 3028 KB Output is correct
25 Correct 5 ms 4180 KB Output is correct
26 Correct 2 ms 3028 KB Output is correct
27 Correct 2 ms 3028 KB Output is correct
28 Correct 2 ms 3156 KB Output is correct
29 Correct 2 ms 3156 KB Output is correct
30 Correct 2 ms 3156 KB Output is correct
31 Correct 3 ms 3264 KB Output is correct
32 Correct 2 ms 3156 KB Output is correct
33 Correct 5 ms 4180 KB Output is correct
34 Correct 4 ms 4180 KB Output is correct
35 Correct 4 ms 4052 KB Output is correct
36 Correct 5 ms 4052 KB Output is correct
37 Correct 4 ms 4052 KB Output is correct
38 Correct 5 ms 4180 KB Output is correct
39 Correct 4 ms 4180 KB Output is correct
40 Correct 4 ms 3848 KB Output is correct
41 Correct 5 ms 4180 KB Output is correct
42 Correct 4 ms 4180 KB Output is correct
43 Correct 395 ms 110384 KB Output is correct
44 Correct 257 ms 115368 KB Output is correct
45 Correct 237 ms 106124 KB Output is correct
46 Correct 332 ms 106112 KB Output is correct
47 Correct 292 ms 106124 KB Output is correct
48 Correct 446 ms 114712 KB Output is correct
49 Correct 240 ms 107212 KB Output is correct
50 Correct 225 ms 95952 KB Output is correct
51 Correct 359 ms 107600 KB Output is correct
52 Correct 287 ms 107656 KB Output is correct
53 Correct 253 ms 117036 KB Output is correct
54 Correct 532 ms 114992 KB Output is correct
55 Correct 236 ms 87052 KB Output is correct
56 Correct 391 ms 111912 KB Output is correct
57 Correct 393 ms 107920 KB Output is correct
58 Correct 384 ms 107648 KB Output is correct
59 Correct 417 ms 107632 KB Output is correct
60 Correct 349 ms 107724 KB Output is correct