oj.uz

Submission #557696

# Submission time Handle Problem Language Result Execution time Memory
557696 2022-05-05T19:53:10 Z status_coding Star Trek (CEOI20_startrek) C++14
30 / 100
 1000 ms 14832 KB 
#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;

nodS nod[100005];

bool win[100005];
long long nrCrit[100005];

long long dp[1005];

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

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

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);
    }

    for(int i=1;i<=n;i++)
    {
        dfs(i, 0);

        win[i] = nod[i].dp;
        nrCrit[i] = nod[i].nrCrit;
    }

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

    for(int i=d-1 ;i>=0; i--)
    {
        long long nrF=0;

        for(int j=1;j<=n;j++)
        {
            nrF += dp[j];
            nrF %= mod;
        }

        for(int j=1;j<=n;j++)
        {
            if(!win[j])
            {
                dp[j] = (n - nrCrit[j]) * n;
                dp[j] %= mod;

                dp[j] += nrCrit[j] * (n - nrF);
                dp[j] %= mod;
            }
            else
            {
                dp[j] = nrCrit[j] * nrF;
                dp[j] %= mod;
            }
        }
    }

    cout<<(put(n, 2*d) - dp[1] + mod) % mod;
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 29 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4316 KB Output is correct
8 Correct 26 ms 4348 KB Output is correct
9 Correct 19 ms 4264 KB Output is correct
10 Correct 24 ms 4256 KB Output is correct
11 Correct 22 ms 4272 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4316 KB Output is correct
8 Correct 26 ms 4348 KB Output is correct
9 Correct 19 ms 4264 KB Output is correct
10 Correct 24 ms 4256 KB Output is correct
11 Correct 22 ms 4272 KB Output is correct
12 Execution timed out 1076 ms 14832 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4316 KB Output is correct
8 Correct 26 ms 4348 KB Output is correct
9 Correct 19 ms 4264 KB Output is correct
10 Correct 24 ms 4256 KB Output is correct
11 Correct 22 ms 4272 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Incorrect 30 ms 4268 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4316 KB Output is correct
8 Correct 26 ms 4348 KB Output is correct
9 Correct 19 ms 4264 KB Output is correct
10 Correct 24 ms 4256 KB Output is correct
11 Correct 22 ms 4272 KB Output is correct
12 Execution timed out 1076 ms 14832 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 29 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -