oj.uz

Submission #557687

# Submission time Handle Problem Language Result Execution time Memory
557687 2022-05-05T19:18:36 Z status_coding Star Trek (CEOI20_startrek) C++14
45 / 100
 118 ms 16852 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;

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 3 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 3 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 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 106 ms 11688 KB Output is correct
13 Correct 118 ms 16852 KB Output is correct
14 Correct 98 ms 7576 KB Output is correct
15 Correct 87 ms 8536 KB Output is correct
16 Correct 84 ms 8572 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Incorrect 3 ms 4180 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 106 ms 11688 KB Output is correct
13 Correct 118 ms 16852 KB Output is correct
14 Correct 98 ms 7576 KB Output is correct
15 Correct 87 ms 8536 KB Output is correct
16 Correct 84 ms 8572 KB Output is correct
17 Correct 2 ms 4180 KB Output is correct
18 Incorrect 3 ms 4180 KB Output isn't correct
19 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 3 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -