oj.uz

Submission #557697

# Submission time Handle Problem Language Result Execution time Memory
557697 2022-05-05T20:04:27 Z status_coding Star Trek (CEOI20_startrek) C++14
30 / 100
 1000 ms 14828 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[100005];

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

        long long nrW = put(n, 2*(d-i-1) + 1 ) - nrF + mod;
        nrW %= mod;

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

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

                dp[j] += nrCrit[j] * nrW;
                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 30 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 3 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 4200 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
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 4200 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
6 Correct 2 ms 4180 KB Output is correct
7 Correct 27 ms 4316 KB Output is correct
8 Correct 32 ms 4308 KB Output is correct
9 Correct 21 ms 4268 KB Output is correct
10 Correct 23 ms 4260 KB Output is correct
11 Correct 23 ms 4264 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 4200 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
6 Correct 2 ms 4180 KB Output is correct
7 Correct 27 ms 4316 KB Output is correct
8 Correct 32 ms 4308 KB Output is correct
9 Correct 21 ms 4268 KB Output is correct
10 Correct 23 ms 4260 KB Output is correct
11 Correct 23 ms 4264 KB Output is correct
12 Execution timed out 1089 ms 14828 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 4200 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
6 Correct 2 ms 4180 KB Output is correct
7 Correct 27 ms 4316 KB Output is correct
8 Correct 32 ms 4308 KB Output is correct
9 Correct 21 ms 4268 KB Output is correct
10 Correct 23 ms 4260 KB Output is correct
11 Correct 23 ms 4264 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Incorrect 29 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 4200 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
6 Correct 2 ms 4180 KB Output is correct
7 Correct 27 ms 4316 KB Output is correct
8 Correct 32 ms 4308 KB Output is correct
9 Correct 21 ms 4268 KB Output is correct
10 Correct 23 ms 4260 KB Output is correct
11 Correct 23 ms 4264 KB Output is correct
12 Execution timed out 1089 ms 14828 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 30 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -