oj.uz

Submission #557561

# Submission time Handle Problem Language Result Execution time Memory
557561 2022-05-05T13:08:54 Z status_coding Star Trek (CEOI20_startrek) C++14
7 / 100
 2 ms 2660 KB 
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

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];
long long nrCritF[100005];

vector<int> v[100005];

bool dp[100005];
int nrFChild[100005];
int nrCrit[100005];

void calcDp(int p, int avoid=0)
{
    nrFChild[p] = 0;
    dp[p] = false;
    nrCrit[p] = 0;

    for(int it : v[p])
    {
        if(it == avoid)
            continue;

        if(!dp[it])
        {
            nrFChild[p] ++;
            dp[p] = true;
        }
    }

    if(!dp[p])
        nrCrit[p] = 1;

    for(int it : v[p])
    {
        if(it == avoid)
            continue;

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

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

void dfs(int p, int par)
{
    for(int it : v[p])
    {
        if(it == par)
            continue;

        dfs(it, p);
    }

    calcDp(p, par);
}

void calc(int p, int par)
{
    win[p] = dp[p];
    nrCritF[p] = nrCrit[p];

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

        calcDp(p, it);
        calcDp(it);

        calc(it, p);

        calcDp(it, p);
        calcDp(p);
    }
}

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;

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

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

    for(int i=1;i<=n;i++)
        cout<<win[i]<<' '<<nrCritF[i]<<'\n';
    return 0;
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -