Submission #1285814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285814		Art	Star Trek (CEOI20_startrek)	C++20	45 / 100	44 ms	12456 KiB

startrek

//      - Art -
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

using namespace std;

int binpow(int a, long long b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = 1LL * res * a % MOD;
        }
        a = 1LL * a * a % MOD; b >>= 1;
    }
    return res;
}

int n;
long long D;
vector<int> adj[N];

namespace subtask_4 {
    bool checkSubtask() {
        return D == 1;
    }

    int numLose[N];
    void dfs(int u, int p) {
        for (int &v : adj[u]) if (v != p) {
            dfs(v, u);
            numLose[u] += !numLose[v];
        }
    }

    bool win[N];
    void reRoot(int u, int p) {
        numLose[u] += !win[p] || (!numLose[u] && numLose[p] == 1);
        win[u] = numLose[u] > 0;
        for (int v : adj[u]) if (v != p) {
            reRoot(v, u);
        }
    }

    int swappable;
    void canSwap(int u, int p) {
        if (numLose[u] > 1) {
            return;
        }
        if (!numLose[u]) {
            ++swappable;
            for (int &v : adj[u]) if (v != p) {
                canSwap(v, u);
            }
            return;
        }
        for (int v : adj[u]) if (v != p && !numLose[v]) {
            canSwap(v, u);
        }
    }

    void solve() {
        dfs(1, 0);
        int cntLose = 0;
        FOR (i, 1, n) {
            cntLose += !numLose[i];
        }
        canSwap(1, 0);
        win[1] = numLose[1] > 0;
        for (int &v : adj[1]) {
            reRoot(v, 1);
        }
        int cntWin = 0;
        FOR (i, 1, n) {
            cntWin += win[i];
        }
        int res = 0;
        if (win[1]) {
            res = (res + 1LL * (n - cntLose) * n) % MOD;
            res = (res + 1LL * (cntLose - swappable) * n) % MOD;
            res = (res + 1LL * swappable * cntWin) % MOD;
        }
        else {
            res = (res + 1LL * swappable * (n - cntWin)) % MOD;
        }
        cout << res, el;
    }
}

namespace subtask_5 {
    bool checkSubtask() {
        return n <= 1000;
    }



    void solve() {

    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> D;
    FOR (i, 2, n) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    if (n == 2) {
        cout << binpow(4, D), el;
        return 0;
    }
    if (subtask_4::checkSubtask()) return subtask_4::solve(), 0;
//    if (subtask_5::checkSubtask()) return subtask_5::solve(), 0;

    return 1;
}

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