oj.uz

Submission #492503

# Submission time Handle Problem Language Result Execution time Memory
492503 2021-12-07T16:01:48 Z LittleCube Star Trek (CEOI20_startrek) C++14
38 / 100
 133 ms 15440 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];
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;
    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 2 ms 2636 KB Output is correct
2 Runtime error 4 ms 5196 KB Execution killed with signal 6

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 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 2 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 2 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 2 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 2 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 100 ms 10952 KB Output is correct
13 Correct 133 ms 15440 KB Output is correct
14 Correct 77 ms 9280 KB Output is correct
15 Correct 89 ms 9212 KB Output is correct
16 Correct 83 ms 9292 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 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 1 ms 2636 KB Output is correct
13 Runtime error 4 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 2 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 2 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 100 ms 10952 KB Output is correct
13 Correct 133 ms 15440 KB Output is correct
14 Correct 77 ms 9280 KB Output is correct
15 Correct 89 ms 9212 KB Output is correct
16 Correct 83 ms 9292 KB Output is correct
17 Correct 1 ms 2636 KB Output is correct
18 Runtime error 4 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 2 ms 2636 KB Output is correct
2 Runtime error 4 ms 5196 KB Execution killed with signal 6