Submission #932420

#	Time	Username	Problem	Language	Result	Execution time	Memory
932420		LucaIlie	Star Trek (CEOI20_startrek)	C++17	43 / 100	1074 ms	15012 KiB

startrek

#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], critical[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 dfsCritical( int u, int p ) {
    critical[u] = (!canWin[u]);
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsCritical( v, u );
        if ( influence( v, u ) )
            critical[u] += critical[v];
    }
}

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

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

        if ( influence( v, u ) )
            critical[u] -= critical[v];
        //printf( "ch %d %d\n", critical[u], critical[v] );
        critical[v] -= (!canWin[v]);
        critical[u] -= (!canWin[u]);
        countChildrenLosers[u] -= (!canWin[v]);
        canWin[u] = (countChildrenLosers[u] > 0);
        countChildrenLosers[v] += (!canWin[u]);
        canWin[v] = (countChildrenLosers[v] > 0);
        critical[v] += (!canWin[v]);
        critical[u] += (!canWin[u]);
        if ( influence( u, v ) )
            critical[v] += critical[u];

        reroot( v, u );

        if ( influence( u, v ) )
            critical[v] -= critical[u];
        critical[v] -= (!canWin[v]);
        critical[u] -= (!canWin[u]);
        countChildrenLosers[v] -= (!canWin[u]);
        canWin[v] = (countChildrenLosers[v] > 0);
        countChildrenLosers[u] += (!canWin[v]);
        canWin[u] = (countChildrenLosers[u] > 0);
        critical[v] += (!canWin[v]);
        critical[u] += (!canWin[u]);
        if ( influence( v, u ) )
            critical[u] += critical[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 );
    dfsCritical( 1, 0 );
    reroot( 1, 0 );

   // cout << "C: " << c << "\n";

    c = 0;
    for ( int r = 1; r <= n; r++ ) {
        dfsGame( r, 0 );
        dfsCritical( r, 0 );
        //cout << r << " " << critical[r] << "\n";
        c += (canWin[r] ? 1 : -1) * critical[r];
    }
    //cout << "C: " << c << "\n";

    while ( c < 0 )
        c += MOD;
    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 );
    dfsCritical( 1, 0 );
    if ( canWin[1] )
        cout << (lgPut( n, 2 * d ) - dp[d - 1] * critical[1] % MOD + MOD) % MOD;
    else
        cout << dp[d - 1] * critical[1] % MOD << "\n";

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15