답안 #492503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492503	2021-12-07T16:01:48 Z	LittleCube	Star Trek (CEOI20_startrek)	C++14	38 / 100	133 ms	15440 KB

startrek

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	Output is correct
2	Runtime error	4 ms	5196 KB	Execution killed with signal 6

답안 #492503

Compilation message