Submission #557574

#	Time	Username	Problem	Language	Result	Execution time	Memory
557574		status_coding	Star Trek (CEOI20_startrek)	C++14	30 / 100	1094 ms	13368 KiB

startrek

#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

long long put(long long baza, long long exp)
{
    if(!exp)
        return 1;

    long long ans = put(baza, exp/2);
    ans *= ans;
    ans %= mod;

    if(exp % 2)
    {
        ans *= baza;
        ans %= mod;
    }

    return ans;
}

long long n,d;

bool win[100005];
long long nrCritF[100005];

vector<int> v[100005];

bool dp[100005];
int nrFChild[100005];
int nrCrit[100005];

void calcDp(int p, int avoid=0)
{
    nrFChild[p] = 0;
    dp[p] = false;
    nrCrit[p] = 0;

    for(int it : v[p])
    {
        if(it == avoid)
            continue;

        if(!dp[it])
        {
            nrFChild[p] ++;
            dp[p] = true;
        }
    }

    if(!dp[p])
        nrCrit[p] = 1;

    for(int it : v[p])
    {
        if(it == avoid)
            continue;

        if(!dp[p] && dp[it])
            nrCrit[p] += nrCrit[it];

        if(dp[p] && !dp[it] && nrFChild[p] == 1)
            nrCrit[p] += nrCrit[it];
    }
}

void dfs(int p, int par)
{
    for(int it : v[p])
    {
        if(it == par)
            continue;

        dfs(it, p);
    }

    calcDp(p, par);
}

void calc(int p, int par)
{
    win[p] = dp[p];
    nrCritF[p] = nrCrit[p];

    for(int it : v[p])
    {
        if(it == par)
            continue;

        calcDp(p, it);
        calcDp(it);

        calc(it, p);

        calcDp(it, p);
        calcDp(p);
    }
}

int main()
{
    cin>>n>>d;

    if(n == 2)
    {
        cout<<put(n, 2*d);
        return 0;
    }

    for(int i=1;i<n;i++)
    {
        int x, y;
        cin>>x>>y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);
    calc(1, 0);

    /*
    for(int i=1;i<=n;i++)
        cout<<win[i]<<' '<<nrCritF[i]<<'\n';
    */

    if(d == 1)
    {
        long long nrF = 0;

        for(int i=1;i<=n;i++)
            if(!win[i])
                nrF++;

        long long ans = 0;

        if(dp[1])
        {
            ans = nrCritF[1] * (n - nrF);
            ans %= mod;

            ans += (n-nrCritF[1]) * n;
            ans %= mod;
        }
        else
        {
            ans = nrCritF[1] * nrF;
            ans %= mod;
        }

        cout<<ans;
        return 0;
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15