oj.uz

Submission #495504

# Submission time Handle Problem Language Result Execution time Memory
495504 2021-12-19T07:34:45 Z LittleCube Star Trek (CEOI20_startrek) C++14
38 / 100
 134 ms 19336 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll MOD = 1000000007;

ll N, D, dp[100005], pre[100005], subtree[100005], crit[100005], L, K, dpL[100005], Npow[100005];
vector<int> E[100005];

void dfs(int k)
{
    for (int i : E[k])
        if (i != pre[k])
        {
            pre[i] = k;
            dfs(i);
            if (dp[i] == 0)
                dp[k]++;
        }
}

void dfs2(int k, bool w)
{
    //cout << "dfs2 " << k << '\n';
    if (w && dp[k] == 1)
        for (int i : E[k])
        {
            if (i != pre[k])
                if (dp[i] == 0)
                {
                    dfs2(i, false);
                    subtree[k] += subtree[i];
                }
        }
    else if (w)
        for (int i : E[k])
        {
            if (i != pre[k])
                dfs2(i, true);
        }
    else if (!w)
    {
        subtree[k]++;
        for (int i : E[k])
            if (i != pre[k])
            {
                dfs2(i, true);
                subtree[k] += subtree[i];
            }
    }
}

void reroot(int k)
{
    //cout << "reroot " << k << '\n';
    //for (int i = 1; i <= N; i++)
    //    cout << subtree[i] << " \n"[i == N];
    //for (int i = 1; i <= N; i++)
    //    cout << dp[i] << " \n"[i == N];
    int sum = 0;
    if (dp[k] == 0)
        crit[k] = 1;
    for (int i : E[k])
    {
        if (dp[k] == 1 && dp[i] == 0)
            crit[k] += subtree[i];
        else if (dp[k] == 0)
            crit[k] += subtree[i];

        if (dp[k] == 2 && dp[i] == 0)
            sum += subtree[i];
        else if (dp[k] == 1 && dp[i] == 1)
            sum += subtree[i];
    }
    swap(subtree[k], crit[k]);
    for (int i : E[k])
        if (i != pre[k])
        {
            if (dp[k] == 1 && dp[i] == 0)
            {
                ll tmp = sum + 1;
                swap(tmp, subtree[k]);
                dp[k]--, dp[i]++;
                reroot(i);
                dp[k]++;
                swap(tmp, subtree[k]);
            }
            else if (dp[k] >= 2 && dp[i] == 0)
            {
                ll tmp = (dp[k] == 2 ? sum - subtree[i] : 0);
                swap(tmp, subtree[k]);
                dp[k]--;
                reroot(i);
                dp[k]++;
                swap(tmp, subtree[k]);
            }
            else if (dp[k] == 0)
            {
                subtree[k] -= subtree[i];
                dp[i]++;
                reroot(i);
                subtree[k] += subtree[i];
            }
            else
                reroot(i);
        }
    swap(subtree[k], crit[k]);
}

signed main()
{
    cin >> N >> D;
    for (int i = 1; i < N; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }

    dfs(1);
    dfs2(1, dp[1] != 0);
    reroot(1);
    //for (int i = 1; i <= N; i++)
    //    cout << crit[i] << " \n"[i == N];
    for (int i = 1; i <= N; i++)
        if (dp[i] == 0)
            L++, K = (K - crit[i] + MOD) % MOD;
        else
            K = (K + crit[i] + MOD) % MOD;
    dpL[0] = L;
    Npow[0] = 1;
    for (int i = 1; i <= D; i++)
    {
        Npow[i] = (Npow[i - 1] * N % MOD) * N % MOD;
        dpL[i] = ((L * Npow[i] % MOD) + (K * dpL[i - 1])) % MOD;
    }
    if (dp[1] == 0)
        cout << (dpL[D - 1] * crit[1]) % MOD << '\n';
    else
        cout << (Npow[D] - (dpL[D - 1] * crit[1]) % MOD + MOD) % MOD << '\n';
}
/*
7 1
1 2
2 3
3 4
4 5
5 6
6 7
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Incorrect 2 ms 2640 KB Output isn't correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2768 KB Output is correct
3 Runtime error 14 ms 14692 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 105 ms 14364 KB Output is correct
13 Correct 134 ms 19336 KB Output is correct
14 Correct 87 ms 10064 KB Output is correct
15 Correct 97 ms 10084 KB Output is correct
16 Correct 99 ms 10020 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2640 KB Output is correct
13 Incorrect 2 ms 2768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 105 ms 14364 KB Output is correct
13 Correct 134 ms 19336 KB Output is correct
14 Correct 87 ms 10064 KB Output is correct
15 Correct 97 ms 10084 KB Output is correct
16 Correct 99 ms 10020 KB Output is correct
17 Correct 2 ms 2640 KB Output is correct
18 Incorrect 2 ms 2768 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Incorrect 2 ms 2640 KB Output isn't correct