oj.uz

Submission #931833

# Submission time Handle Problem Language Result Execution time Memory
931833 2024-02-22T11:48:05 Z LucaIlie Star Trek (CEOI20_startrek) C++17
23 / 100
 1000 ms 18256 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAX_N = 1e5;
const int MAX_D = 1e5;
const int MOD = 1e9 + 7;
bool canWin[MAX_N + 1];
int countChildrenLosers[MAX_N + 1], add[MAX_N + 1], reach[MAX_N + 1], dp[MAX_D][3];
vector<int> adj[MAX_N + 1];

void dfsGame( int u, int p ) {
    canWin[u] = false;
    countChildrenLosers[u] = 0;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsGame( v, u );
        canWin[u] |= (!canWin[v]);
        countChildrenLosers[u] += (!canWin[v]);
    }
}

void dfsCalcAdd( int u, int p ) {
    if ( p == 0 ) {
        add[u] = (canWin[u] ? -1 : 1);
        reach[u] = u;
    } else {
        if ( canWin[u] ) {
            if ( canWin[p] ) {
                add[u] = -1;
                reach[u] = u;
            } else {
                add[u] = add[p] - 1;
                reach[u] = reach[p];
            }
        } else {
            if ( countChildrenLosers[p] >= 2 ) {
                add[u] = 1;
                reach[u] = u;
            } else {
                add[u] = add[p] + 1;
                reach[u] = reach[p];
            }
        }
    }

    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsCalcAdd( v, u );
    }
}

signed main() {
    int n, d;

    cin >> n >> d;

    if( d != 1 )
        return 1;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
        /*adj[u + n].push_back( v + n );
        adj[v + n].push_back( u + n );
        adj[u + 2 * n].push_back( v + 2 * n );
        adj[v + 2 * n].push_back( u + 2 * n );*/
    }

    /*int ans = 0;
    for ( int u = 1; u <= n; u++ ) {
        for ( int v = n + 1; v <= 2 * n; v++ ) {
            adj[u].push_back( v );
            adj[v].push_back( u );
            for ( int w = n + 1; w <= 2 * n; w++ ) {
                for ( int t = 2 * n + 1; t <= 3 * n; t++ ) {
                    adj[w].push_back( t );
                    adj[t].push_back( w );
                    dfsGame( 1, 0 );
                    if ( canWin[1] ) {
                        ans++;
                        printf( "%d-%d %d-%d\n", u, v, w, t );
                    }
                    adj[w].pop_back();
                    adj[t].pop_back();
                }
            }
            adj[u].pop_back();
            adj[v].pop_back();
        }
    }
    cout << ans;*/

    int pom = 0;
    int winners = 0;
    for ( int v = 1; v <= n; v++ ) {
        dfsGame( v, 0 );
        winners += canWin[v];
        int w = 0;
        for  ( int u = 1; u <= n; u++ )
            w += canWin[u];
        if (pom == 0)
            pom = w;
        if ( pom != w )
            exit( 1 );
    }

    dfsGame( 1, 0 );
    dfsCalcAdd( 1, 0 );

    int countAdd1 = 0;
    for ( int v = 1; v <= n; v++ )
        countAdd1 += (add[v] == 1);//, printf( "%d %d\n", v, add[v] );

    dp[0][0] = 1;
    for ( int i = 1; i < d; i++ ) {
        for ( int a = 0; a < 2; a++ ) {
            int add1 = countAdd1 * (n - (winners + a)) % MOD;
            int add0 = (n * n - add1 + MOD) % MOD;

            dp[i][0] = (dp[i][0] + dp[i - 1][a] * add0) % MOD;
            dp[i][1] = (dp[i][1] + dp[i - 1][a] * add1) % MOD;
        }
        //printf( "%d %d\n", dp[i][0], dp[i][1] );
    }

    int ans = 0;
    for ( int a = 0; a < 2; a++ ) {
        for ( int v = 1; v <= n; v++ ) {
            if ( canWin[1] ) {
                if ( canWin[v] )
                    ans = (ans + n * dp[d - 1][a]) % MOD;
                else {
                    ans = (ans + (winners + a) * dp[d - 1][a]) % MOD;
                    if ( reach[v] != 1 )
                        ans = (ans + (n - winners - a) * dp[d - 1][a]) % MOD;
                }
            } else {
                if ( !canWin[v] ) {
                    if ( reach[v] == 1 )
                        ans = (ans + (n - winners - a) * dp[d - 1][a]) % MOD;
                }
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Runtime error 1 ms 4700 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 4700 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 12 ms 6744 KB Output is correct
8 Correct 14 ms 6748 KB Output is correct
9 Correct 8 ms 6820 KB Output is correct
10 Correct 10 ms 6824 KB Output is correct
11 Correct 10 ms 6784 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 12 ms 6744 KB Output is correct
8 Correct 14 ms 6748 KB Output is correct
9 Correct 8 ms 6820 KB Output is correct
10 Correct 10 ms 6824 KB Output is correct
11 Correct 10 ms 6784 KB Output is correct
12 Execution timed out 1030 ms 18256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 12 ms 6744 KB Output is correct
8 Correct 14 ms 6748 KB Output is correct
9 Correct 8 ms 6820 KB Output is correct
10 Correct 10 ms 6824 KB Output is correct
11 Correct 10 ms 6784 KB Output is correct
12 Correct 1 ms 6744 KB Output is correct
13 Runtime error 1 ms 4700 KB Execution failed because the return code was nonzero
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 12 ms 6744 KB Output is correct
8 Correct 14 ms 6748 KB Output is correct
9 Correct 8 ms 6820 KB Output is correct
10 Correct 10 ms 6824 KB Output is correct
11 Correct 10 ms 6784 KB Output is correct
12 Execution timed out 1030 ms 18256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Runtime error 1 ms 4700 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -