oj.uz

Submission #557701

# Submission time Handle Problem Language Result Execution time Memory
557701 2022-05-05T20:30:46 Z status_coding Star Trek (CEOI20_startrek) C++14
50 / 100
 1000 ms 14748 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]) * (nrF + nrW);
                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 Correct 28 ms 4360 KB Output is correct

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 3 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 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 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 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4320 KB Output is correct
8 Correct 29 ms 4352 KB Output is correct
9 Correct 17 ms 4264 KB Output is correct
10 Correct 22 ms 4260 KB Output is correct
11 Correct 22 ms 4200 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 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4320 KB Output is correct
8 Correct 29 ms 4352 KB Output is correct
9 Correct 17 ms 4264 KB Output is correct
10 Correct 22 ms 4260 KB Output is correct
11 Correct 22 ms 4200 KB Output is correct
12 Execution timed out 1084 ms 14748 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
20.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 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4320 KB Output is correct
8 Correct 29 ms 4352 KB Output is correct
9 Correct 17 ms 4264 KB Output is correct
10 Correct 22 ms 4260 KB Output is correct
11 Correct 22 ms 4200 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Correct 28 ms 4180 KB Output is correct
14 Correct 2 ms 4180 KB Output is correct
15 Correct 2 ms 4180 KB Output is correct
16 Correct 2 ms 4180 KB Output is correct
17 Correct 3 ms 4216 KB Output is correct
18 Correct 3 ms 4224 KB Output is correct
19 Correct 2 ms 4180 KB Output is correct
20 Correct 2 ms 4180 KB Output is correct
21 Correct 23 ms 4316 KB Output is correct
22 Correct 26 ms 4308 KB Output is correct
23 Correct 18 ms 4272 KB Output is correct
24 Correct 23 ms 4272 KB Output is correct
25 Correct 23 ms 4272 KB Output is correct
26 Correct 546 ms 4224 KB Output is correct
27 Correct 562 ms 4356 KB Output is correct
28 Correct 557 ms 4260 KB Output is correct
29 Correct 545 ms 4264 KB Output is correct
30 Correct 406 ms 4264 KB Output is correct

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 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 23 ms 4320 KB Output is correct
8 Correct 29 ms 4352 KB Output is correct
9 Correct 17 ms 4264 KB Output is correct
10 Correct 22 ms 4260 KB Output is correct
11 Correct 22 ms 4200 KB Output is correct
12 Execution timed out 1084 ms 14748 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 Correct 28 ms 4360 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 3 ms 4180 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 3 ms 4180 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct
14 Correct 23 ms 4320 KB Output is correct
15 Correct 29 ms 4352 KB Output is correct
16 Correct 17 ms 4264 KB Output is correct
17 Correct 22 ms 4260 KB Output is correct
18 Correct 22 ms 4200 KB Output is correct
19 Execution timed out 1084 ms 14748 KB Time limit exceeded
20 Halted 0 ms 0 KB -