Submission #557687

#	Time	Username	Problem	Language	Result	Execution time	Memory
557687		status_coding	Star Trek (CEOI20_startrek)	C++14	45 / 100	118 ms	16852 KiB

startrek

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

using namespace std;

struct nodS
{
    bool dp;
    int nrFChild, nrCrit;
    vector<int> v;
};

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];

nodS nod[100005];

void addChild(int p, int it)
{
    if(!nod[it].dp)
    {
        nod[p].nrFChild ++;
        nod[p].dp = true;
    }
}

void delChild(int p, int it)
{
    if(!nod[it].dp)
    {
        nod[p].nrFChild --;

        if(!nod[p].nrFChild)
            nod[p].dp = false;
    }
}

void dfs(int p, int par)
{
    nod[p].nrFChild = 0;
    nod[p].nrCrit = 0;

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

        dfs(it, p);

        addChild(p, it);
    }

    nod[p].dp = (nod[p].nrFChild > 0);

    if(!nod[p].dp)
        nod[p].nrCrit = 1;
    else
        nod[p].nrCrit = 0;

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

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

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

void calc(int p, int par)
{
    win[p] = nod[p].dp;

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

        delChild(p, it);
        addChild(it, p);

        calc(it, p);

        delChild(it, p);
        addChild(p, it);
    }
}

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;

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

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

    long long ans = 0;
    long long nrCrit = nod[1].nrCrit;
    long long nrF = 0;

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

    //cout<<nrF<<' '<<nrCrit<<'\n';

    if(win[1])
    {
        ans = (n - nrCrit) * n;
        ans %= mod;

        ans += nrCrit * (n - nrF);
        ans %= mod;
    }
    else
    {
        ans = nrCrit * nrF;
        ans %= mod;
    }

    cout<<ans;
    return 0;
}

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