oj.uz

Submission #492512

# Submission time Handle Problem Language Result Execution time Memory
492512 2021-12-07T16:35:03 Z LittleCube Star Trek (CEOI20_startrek) C++14
38 / 100
 119 ms 14460 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][2], pre[100005], ans;
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] == 0 && dp[k][0] == 0)
                dp[k][0] = i;
            else if (dp[i][0] == 0)
                dp[k][1] = i;
        }
}

void reroot(int k)
{
    for (int i : E[k])
        if (i != pre[k])
        {
            if ((dp[k][0] == 0) || (dp[k][0] == i && dp[k][1] == 0))
            {
                if (dp[i][0] == 0)
                    dp[i][0] = k;
                else
                    dp[i][1] = k;
            }
            reroot(i);
        }
}

ll dfs2(int k, bool first)
{
    if (first)
        if (dp[k][1] != 0)
            return 0;
        else
            return dfs2(dp[k][0], false);
    else
    {
        int ans = 1;
        for (int i : E[k])
            if (i != pre[k])
                ans += dfs2(i, true);
        return ans;
    }
}

signed main()
{
    cin >> N >> D;
    if (N == 2)
    {
        ll p = D % (MOD - 1), b = 4;
        while (p)
        {
            if (p & 1)
                ans = (ans * b) % MOD;
            p >>= 1;
            b = b * b % MOD;
        }
        cout << ans << '\n';
        return 0;
    }
    assert(D == 1);
    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);
    ll cnt = dfs2(1, dp[1][0] != 0);
    reroot(1);
    ll lose = 0;
    for (int i = 1; i <= N; i++)
        if (dp[i][0] == 0)
        {
            lose++;
            //cerr << i << '\n';
        }
    if (dp[1][0])
        cout << (N * N - cnt * lose) % MOD << '\n';
    else
        cout << (cnt * lose) % MOD << '\n';
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Runtime error 4 ms 5164 KB Execution killed with signal 6

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 102 ms 10956 KB Output is correct
13 Correct 119 ms 14460 KB Output is correct
14 Correct 72 ms 8312 KB Output is correct
15 Correct 103 ms 8280 KB Output is correct
16 Correct 94 ms 8196 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Runtime error 3 ms 5196 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 102 ms 10956 KB Output is correct
13 Correct 119 ms 14460 KB Output is correct
14 Correct 72 ms 8312 KB Output is correct
15 Correct 103 ms 8280 KB Output is correct
16 Correct 94 ms 8196 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Runtime error 3 ms 5196 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Runtime error 4 ms 5164 KB Execution killed with signal 6