Submission #932400

#	Time	Username	Problem	Language	Result	Execution time	Memory
932400		LucaIlie	Star Trek (CEOI20_startrek)	C++17	0 / 100	1 ms	4700 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]);
    }
}

void dfsCalcReach( int u, int p ) {
    if ( p == 0 )
        reach[u] = u;
    else {
        if ( canWin[u] ) {
            if ( canWin[p] )
                reach[u] = u;
            else
                reach[u] = reach[p];
        } else {
            if ( countChildrenLosers[p] >= 2 )
                reach[u] = u;
            else
                reach[u] = reach[p];
        }
    }

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

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

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

        countChildrenLosers[u] -= (!canWin[v]);
        canWin[u] = (countChildrenLosers[u] > 0);
        countChildrenLosers[v] += (!canWin[u]);
        canWin[v] = (countChildrenLosers[v] > 0);

        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 );
    dfsCalcReach( 1, 0 );
    reroot( 1, 0 );
    /*for ( int r = 1; r <= n; r++ ) {
        dfsGame( r, 0 );
        dfsCalcAdd( r, 0 );
        losers += !canWin[r];
        winners += canWin[r];
        reach1[r] = 0;
        for ( int v = 1; v <= n; v++ ) {
            if ( !canWin[v] && reach[v] == r )
                reach1[r]++;
        }
        rch += (canWin[r] ? 1 : -1) * reach1[r];
    }*/

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

    dfsGame( 1, 0 );
    dfsCalcReach( 1, 0 );
    for ( int v = 1; v <= n; v++ ) {
        if ( !canWin[v] && reach[v] == 1 )
            critical[1]++;
    }
    reroot( 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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15