oj.uz

Submission #856816

# Submission time Handle Problem Language Result Execution time Memory
856816 2023-10-04T16:29:24 Z sofijavelkovska Star Trek (CEOI20_startrek) C++14
45 / 100
 75 ms 15476 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5, MOD=1e9+7;

vector<int> adj[MAXN+1];
bool win0[MAXN+1], win1[MAXN+1];
int losechildren[MAXN+1];

long long power4(long long n)
{
    long long result=1, current=4;
    for (long long i=0; i<64; i++)
    {
        if (n&((long long)1<<i))
            result=result*current%MOD;
        current=current*current%MOD;
    }

    return result;
}

bool dfs0(int x, int t)
{
    bool possible=false;
    for (auto y : adj[x])
    {
        if (y==t)
            continue;
        if (!dfs0(y, x))
            possible=true;
    }

    return win0[x]=possible;
}

void dfs1(int x, int t)
{
    if (t==-1)
    {
        win1[x]=win0[x];
        for (auto y : adj[x])
        {
            if (y==t)
                continue;
            dfs1(y, x);
        }

        return;
    }
    int memox=losechildren[x];
    int memot=losechildren[t];
    if (!win0[x])
        losechildren[t]=losechildren[t]-1;
    if (losechildren[t]==0)
        losechildren[x]=losechildren[x]+1;
    if (losechildren[x]>0)
        win1[x]=true;
    else
        win1[x]=false;
    for (auto y : adj[x])
    {
        if (y==t)
            continue;
        dfs1(y, x);
    }
    losechildren[x]=memox;
    losechildren[t]=memot;

    return;
}

int dfscritical(int x, int t)
{
    int critical=0;
    if (!win0[x])
    {
        critical=critical+1;
        for (auto y : adj[x])
        {
            if (y==t)
                continue;
            critical=critical+dfscritical(y, x);
        }
    }
    else
    {
        int losenodes=0;
        for (auto y : adj[x])
        {
            if (y==t)
                continue;
            if (!win0[y])
            {
                critical=critical+dfscritical(y, x);
                losenodes=losenodes+1;
            }
        }
        if (losenodes>1)
            critical=0;
    }

    return critical;
}

void countlosechildren(int x, int t)
{
    losechildren[x]=0;
    for (auto y : adj[x])
    {
        if (y==t)
            continue;
        countlosechildren(y, x);
        if (!win0[y])
            losechildren[x]=losechildren[x]+1;
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, x, y, total, i;
    long long d;
    cin >> n >> d;
    for (i=0; i<n-1; i++)
    {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    if (n==2)
    {
        cout << power4(d);
        return 0;
    }
    dfs0(1, -1);
    countlosechildren(1, -1);
    dfs1(1, -1);
    int win=0;
    for (i=1; i<=n; i++)
        if (win1[i])
            win=win+1;
    int lose=n-win;
    int critical=dfscritical(1, -1);
    if (win0[1])
        total=((long long)n*win+(long long)(n-critical)*lose)%MOD;
    else
        total=(long long)critical*lose%MOD;

    cout << total;

    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3160 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3160 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 34 ms 10068 KB Output is correct
13 Correct 75 ms 15476 KB Output is correct
14 Correct 25 ms 7640 KB Output is correct
15 Correct 36 ms 7712 KB Output is correct
16 Correct 39 ms 7600 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3160 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 1 ms 3220 KB Output is correct
13 Incorrect 1 ms 3164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3160 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 34 ms 10068 KB Output is correct
13 Correct 75 ms 15476 KB Output is correct
14 Correct 25 ms 7640 KB Output is correct
15 Correct 36 ms 7712 KB Output is correct
16 Correct 39 ms 7600 KB Output is correct
17 Correct 1 ms 3220 KB Output is correct
18 Incorrect 1 ms 3164 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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