oj.uz

Submission #932414

# Submission time Handle Problem Language Result Execution time Memory
932414 2024-02-23T09:56:28 Z LucaIlie Star Trek (CEOI20_startrek) C++17
38 / 100
 101 ms 16976 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], reach[MAX_N + 1], frecv[MAX_N + 1], dp[MAX_D];
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]);
    }
}


bool influence( int u, int p ) {
    if ( p == 0 )
        return false;

    if ( canWin[u] ) {
        if ( canWin[p] )
            return false;
        return true;
    }

    if ( countChildrenLosers[p] >= 2 )
        return false;
    return true;
}

void dfsCalcReach( int u, int p ) {
    reach[u] = (influence( u, p ) ? reach[p] : u);
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsCalcReach( v, u );
    }
}

void dfsCalcFrecv( int u, int p ) {
    frecv[u] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsCalcFrecv( v, u );
        if ( reach[v] == reach[u] )
            frecv[u] += frecv[v];
    }
}

int losers = 0, c = 0;
void reroot( int u, int p ) {
    losers += !canWin[u];
    c = (c + (canWin[u] ? 1 : -1) * frecv[u] + MOD) % MOD;
    /*for ( int v = 1; v <= 3; v++ )
        printf( "%d ", frecv[v] );
    printf( "\n" );*/

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

        if ( influence( v, u ) )
            frecv[u] -= frecv[v];
        countChildrenLosers[u] -= (!canWin[v]);
        canWin[u] = (countChildrenLosers[u] > 0);
        countChildrenLosers[v] += (!canWin[u]);
        canWin[v] = (countChildrenLosers[v] > 0);
        if ( influence( u, v ) )
            frecv[v] += frecv[u];

        reroot( v, u );

        if ( influence( u, v ) )
            frecv[v] += frecv[u];
        countChildrenLosers[v] -= (!canWin[u]);
        canWin[v] = (countChildrenLosers[v] > 0);
        countChildrenLosers[u] += (!canWin[v]);
        canWin[u] = (countChildrenLosers[u] > 0);
        if ( influence( v, u ) )
            frecv[u] -= frecv[v];
    }
}

int lgPut( int x, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgPut( x, n / 2 );
    p = (long long)p * p % MOD;
    if ( n % 2 == 1 )
        p = (long long)p * x % MOD;

    return p;
}

signed main() {
    int n, d;

    cin >> n >> d;

    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    dfsGame( 1, 0 );
    dfsCalcReach( 1, 0 );
    dfsCalcFrecv( 1, 0 );
    reroot( 1, 0 );

    /*c = 0;
    for ( int r = 1; r <= n; r++ ) {
        dfsGame( r, 0 );
        dfsCalcReach( r, 0 );
        for ( int v = 1; v <= n; v++ ) {
            if ( !canWin[v] && reach[v] == r )
                c += (canWin[r] ? 1 : -1);
        }
        cout << losers << "\n";
    }*/

    dp[0] = losers;
    for ( int i = 1; i < d; i++ )
        dp[i] = (losers * lgPut( n, 2 * i ) + c * dp[i - 1]) % MOD;

    dfsGame( 1, 0 );
    dfsCalcReach( 1, 0 );
    int ans = (canWin[1] ? 0 : lgPut( n, 2 * d ) );
    for ( int v = 1; v <= n; v++ ) {
        if ( canWin[1] ) {
            if ( !canWin[v] && reach[v] == 1 )
                ans = (ans + dp[d - 1]) % MOD;
        } else {
            if ( !canWin[v] && reach[v] == 1 )
                ans = (ans - dp[d - 1]) % MOD;
        }
    }

    cout << (lgPut( n, 2 * d ) - ans + MOD) % MOD << "\n";

    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Runtime error 52 ms 11624 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 83 ms 12772 KB Output is correct
13 Correct 101 ms 16976 KB Output is correct
14 Correct 55 ms 9332 KB Output is correct
15 Correct 69 ms 9300 KB Output is correct
16 Correct 70 ms 9556 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Incorrect 2 ms 4700 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 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 83 ms 12772 KB Output is correct
13 Correct 101 ms 16976 KB Output is correct
14 Correct 55 ms 9332 KB Output is correct
15 Correct 69 ms 9300 KB Output is correct
16 Correct 70 ms 9556 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Incorrect 2 ms 4700 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 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -