Submission #932427

#	Time	Username	Problem	Language	Result	Execution time	Memory
932427		LucaIlie	Star Trek (CEOI20_startrek)	C++17	43 / 100	1036 ms	16268 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], critical[MAX_N + 1], sumCriticalW[MAX_N + 1], sumCriticalL[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];
    }
}

void calcCritical( int u ) {
    if ( canWin[u] ) {
        if ( countChildrenLosers[u] >= 2 )
            critical[u] = 0;
        else
            critical[u] = sumCriticalL[u];
    } else
        critical[u] = sumCriticalW[u] + 1;
}

void dfsCritical( int u, int p ) {
    sumCriticalW[u] = sumCriticalL[u] = 0;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsCritical( v, u );
        if ( canWin[v] )
            sumCriticalW[u] += critical[v];
        else
            sumCriticalL[u] += critical[v];
    }
    calcCritical( u );
}

void reroot( int u, int v ) {
    if ( canWin[v] )
        sumCriticalW[u] -= critical[v];
    else {
        sumCriticalL[u] -= critical[v];
        countChildrenLosers[u]--;
    }
    canWin[u] = (countChildrenLosers[u] > 0);
    calcCritical( u );

    if ( canWin[u] )
        sumCriticalW[v] += critical[u];
    else {
        sumCriticalL[v] += critical[u];
        countChildrenLosers[v]++;
    }
    canWin[v] = (countChildrenLosers[v] > 0);
    calcCritical( v );
}

int losers = 0, c = 0;
void dfs( int u, int p ) {
    losers += !canWin[u];
    c += (canWin[u] ? 1 : -1) * critical[u];

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

        reroot( u, v );
        dfs( v, u );
        reroot( v, u );
    }
}

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 );
    dfs( 1, 0 );*/

    c = 0;
    for ( int r = 1; r <= n; r++ ) {
        dfsGame( r, 0 );
        dfsCritical( r, 0 );
        c += (canWin[r] ? 1 : -1) * critical[r];
        losers += !canWin[r];
    }

    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