oj.uz

Submission #577356

# Submission time Handle Problem Language Result Execution time Memory
577356 2022-06-14T15:20:04 Z piOOE Star Trek (CEOI20_startrek) C++17
65 / 100
 1000 ms 19856 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100000, mod = 1e9 + 7;

int add(int a, int b) {
    return a + b < mod ? a + b : a + b - mod;
}

int mul(int a, int b) {
    return a * (ll) b % mod;
}

int binpow(int a, ll p) {
    int ans = 1;
    for (; p > 0; p >>= 1, a = mul(a, a)) {
        if (p & 1) {
            ans = mul(ans, a);
        }
    }
    return ans;
}

int sub(int a, int b) {
    return a >= b ? a - b : a - b + mod;
}

int n;
ll d;

vector<int> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> d;
    if (n == 2) {
        cout << binpow(4, d);
        return 0;
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if (d == 1) {
        vector<bool> canWin(n), whatIf(n);
        vector<int> cntLoosing(n);

        function<void(int, int)> dfs1 = [&](int v, int p) {
            canWin[v] = false;
            for (int to: g[v]) {
                if (to != p) {
                    dfs1(to, v);
                    if (!canWin[to]) {
                        canWin[v] = true;
                    }
                }
            }
        };

        dfs1(0, -1);

        function<void(int, int)> dfs2 = [&](int v, int p) {
            cntLoosing[v] = 0;
            for (int to: g[v]) {
                if (to != p) {
                    cntLoosing[v] += !canWin[to];
                }
            }
            if (p == -1) {
                whatIf[v] = true;
            } else {
                if (canWin[v]) {
                    if (!canWin[p]) {
                        whatIf[v] = whatIf[p];
                    }
                } else {
                    if (cntLoosing[p] == 1) {
                        whatIf[v] = whatIf[p];
                    }
                }
            }
            for (int to: g[v]) {
                if (to != p) {
                    dfs2(to, v);
                }
            }
        };

        dfs2(0, -1);

        auto sub = canWin;

        function<void(int, int)> dfs3 = [&](int v, int p) {
            cntLoosing[v] = 0;
            for (int to: g[v]) {
                if (to != p) {
                    cntLoosing[v] += !canWin[to];
                } else if (!canWin[p] || cntLoosing[p] == 1 && !canWin[v]) {
                    cntLoosing[v] += 1;
                }
            }
            canWin[v] = cntLoosing[v];
            for (int to: g[v]) {
                if (to != p) {
                    dfs3(to, v);
                }
            }
        };

        dfs3(0, -1);

        int cntWin = count(canWin.begin(), canWin.end(), true);
        int ans = canWin[0] * mul(cntWin, n);
        if (sub[0]) {
            for (int i = 0; i < n; ++i) {
                if (!sub[i] && !whatIf[i] || sub[i]) {
                    ans = add(ans, n - cntWin);
                }
            }
        } else {
            for (int i = 0; i < n; ++i) {
                if (!sub[i] && whatIf[i]) {
                    ans = add(ans, n - cntWin);
                }
            }
        }
        cout << ans;
    } else {
        vector<int> num(n);
        for (int root = 0; root < n; ++root) {
            vector<bool> canWin(n), whatIf(n);
            vector<int> cntLoosing(n);

            function<void(int, int)> dfs1 = [&](int v, int p) {
                canWin[v] = false;
                for (int to: g[v]) {
                    if (to != p) {
                        dfs1(to, v);
                        if (!canWin[to]) {
                            canWin[v] = true;
                        }
                    }
                }
            };

            dfs1(root, -1);

            function<void(int, int)> dfs2 = [&](int v, int p) {
                cntLoosing[v] = 0;
                for (int to: g[v]) {
                    if (to != p) {
                        cntLoosing[v] += !canWin[to];
                    }
                }
                if (p == -1) {
                    whatIf[v] = true;
                } else {
                    if (canWin[v]) {
                        if (!canWin[p]) {
                            whatIf[v] = whatIf[p];
                        }
                    } else {
                        if (cntLoosing[p] == 1) {
                            whatIf[v] = whatIf[p];
                        }
                    }
                }
                for (int to: g[v]) {
                    if (to != p) {
                        dfs2(to, v);
                    }
                }
            };

            dfs2(root, -1);

            auto sub = canWin;

            function<void(int, int)> dfs3 = [&](int v, int p) {
                cntLoosing[v] = 0;
                for (int to: g[v]) {
                    if (to != p) {
                        cntLoosing[v] += !canWin[to];
                    } else if (!canWin[p] || cntLoosing[p] == 1 && !canWin[v]) {
                        cntLoosing[v] += 1;
                    }
                }
                canWin[v] = cntLoosing[v];
                for (int to: g[v]) {
                    if (to != p) {
                        dfs3(to, v);
                    }
                }
            };

            dfs3(root, -1);

            int cntWin = count(canWin.begin(), canWin.end(), true);
            if (sub[root]) {
                for (int i = 0; i < n; ++i) {
                    if (!sub[i] && !whatIf[i] || sub[i]) {
                        num[root] = add(num[root], 1);
                    }
                }
            } else {
                for (int i = 0; i < n; ++i) {
                    if (!sub[i] && whatIf[i]) {
                        num[root] = add(num[root], 1);
                    }
                }
            }
        }
        vector<bool> canWin(n), whatIf(n);
        vector<int> cntLoosing(n);

        function<void(int, int)> dfs1 = [&](int v, int p) {
            canWin[v] = false;
            for (int to: g[v]) {
                if (to != p) {
                    dfs1(to, v);
                    if (!canWin[to]) {
                        canWin[v] = true;
                    }
                }
            }
        };

        dfs1(0, -1);

        function<void(int, int)> dfs2 = [&](int v, int p) {
            cntLoosing[v] = 0;
            for (int to: g[v]) {
                if (to != p) {
                    cntLoosing[v] += !canWin[to];
                }
            }
            if (p == -1) {
                whatIf[v] = true;
            } else {
                if (canWin[v]) {
                    if (!canWin[p]) {
                        whatIf[v] = whatIf[p];
                    }
                } else {
                    if (cntLoosing[p] == 1) {
                        whatIf[v] = whatIf[p];
                    }
                }
            }
            for (int to: g[v]) {
                if (to != p) {
                    dfs2(to, v);
                }
            }
        };

        dfs2(0, -1);

        function<void(int, int)> dfs3 = [&](int v, int p) {
            cntLoosing[v] = 0;
            for (int to: g[v]) {
                if (to != p) {
                    cntLoosing[v] += !canWin[to];
                } else if (!canWin[p] || cntLoosing[p] == 1 && !canWin[v]) {
                    cntLoosing[v] += 1;
                }
            }
            canWin[v] = cntLoosing[v];
            for (int to: g[v]) {
                if (to != p) {
                    dfs3(to, v);
                }
            }
        };

        dfs3(0, -1);
        vector<int> dp(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = canWin[i];
        }
        for (int iter = 1; iter <= d; ++iter) {
            int prv = binpow(mul(n, n), iter - 1);
            int cntWin = 0;
            for (int i = 0; i < n; ++i) {
                cntWin = add(cntWin, dp[i]);
            }
            int cntLoose = sub(mul(n, prv), cntWin);
            for (int i = 0; i < n; ++i) {
                dp[i] = add(canWin[i] * mul(cntWin, n), mul(num[i], cntLoose));
            }
        }
        cout << dp[0];
    }
    return 0;
}

Compilation message

startrek.cpp: In lambda function:
startrek.cpp:105:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  105 |                 } else if (!canWin[p] || cntLoosing[p] == 1 && !canWin[v]) {
startrek.cpp: In function 'int main()':
startrek.cpp:123:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  123 |                 if (!sub[i] && !whatIf[i] || sub[i]) {
      |                     ~~~~~~~~^~~~~~~~~~~~~
startrek.cpp: In lambda function:
startrek.cpp:191:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  191 |                     } else if (!canWin[p] || cntLoosing[p] == 1 && !canWin[v]) {
startrek.cpp: In function 'int main()':
startrek.cpp:208:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  208 |                     if (!sub[i] && !whatIf[i] || sub[i]) {
      |                         ~~~~~~~~^~~~~~~~~~~~~
startrek.cpp:205:17: warning: unused variable 'cntWin' [-Wunused-variable]
  205 |             int cntWin = count(canWin.begin(), canWin.end(), true);
      |                 ^~~~~~
startrek.cpp: In lambda function:
startrek.cpp:271:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  271 |                 } else if (!canWin[p] || cntLoosing[p] == 1 && !canWin[v]) {

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 85 ms 2700 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2672 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2672 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 85 ms 13028 KB Output is correct
13 Correct 77 ms 19856 KB Output is correct
14 Correct 38 ms 7332 KB Output is correct
15 Correct 67 ms 7424 KB Output is correct
16 Correct 58 ms 7456 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2672 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 87 ms 2700 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2664 KB Output is correct
17 Correct 2 ms 2604 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2772 KB Output is correct
22 Correct 2 ms 2772 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 568 ms 2744 KB Output is correct
27 Correct 646 ms 2948 KB Output is correct
28 Correct 509 ms 2676 KB Output is correct
29 Correct 560 ms 2828 KB Output is correct
30 Correct 411 ms 2700 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2672 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 85 ms 13028 KB Output is correct
13 Correct 77 ms 19856 KB Output is correct
14 Correct 38 ms 7332 KB Output is correct
15 Correct 67 ms 7424 KB Output is correct
16 Correct 58 ms 7456 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 87 ms 2700 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2664 KB Output is correct
22 Correct 2 ms 2604 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 2 ms 2772 KB Output is correct
28 Correct 2 ms 2644 KB Output is correct
29 Correct 2 ms 2644 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 568 ms 2744 KB Output is correct
32 Correct 646 ms 2948 KB Output is correct
33 Correct 509 ms 2676 KB Output is correct
34 Correct 560 ms 2828 KB Output is correct
35 Correct 411 ms 2700 KB Output is correct
36 Correct 72 ms 13052 KB Output is correct
37 Correct 66 ms 19852 KB Output is correct
38 Correct 39 ms 7312 KB Output is correct
39 Correct 52 ms 7396 KB Output is correct
40 Correct 76 ms 7384 KB Output is correct
41 Execution timed out 1067 ms 17032 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 85 ms 2700 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2612 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2672 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 2672 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2676 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 3 ms 2644 KB Output is correct
19 Correct 85 ms 13028 KB Output is correct
20 Correct 77 ms 19856 KB Output is correct
21 Correct 38 ms 7332 KB Output is correct
22 Correct 67 ms 7424 KB Output is correct
23 Correct 58 ms 7456 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 87 ms 2700 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 2 ms 2664 KB Output is correct
29 Correct 2 ms 2604 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 2 ms 2644 KB Output is correct
33 Correct 2 ms 2772 KB Output is correct
34 Correct 2 ms 2772 KB Output is correct
35 Correct 2 ms 2644 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 568 ms 2744 KB Output is correct
39 Correct 646 ms 2948 KB Output is correct
40 Correct 509 ms 2676 KB Output is correct
41 Correct 560 ms 2828 KB Output is correct
42 Correct 411 ms 2700 KB Output is correct
43 Correct 72 ms 13052 KB Output is correct
44 Correct 66 ms 19852 KB Output is correct
45 Correct 39 ms 7312 KB Output is correct
46 Correct 52 ms 7396 KB Output is correct
47 Correct 76 ms 7384 KB Output is correct
48 Execution timed out 1067 ms 17032 KB Time limit exceeded
49 Halted 0 ms 0 KB -