제출 #759844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759844		resting	Star Trek (CEOI20_startrek)	C++17	8 / 100	3 ms	2772 KiB

startrek

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mx = 1e5 + 5;

int sz[mx]{};
int cnt2[mx]{};
int win2[mx]{};
int cnt[mx]{};
int win[mx]{};
bool vis[mx]{};
vector<int> adj[mx]{};

int dfs(int v, int p) {
    if (vis[v]) return 0;
    sz[v] = 1;
    for (auto& x : adj[v])
        if (x != p)
            sz[v] += dfs(x, v);
    return sz[v];
}

void dfs2(int v, int p) {
    //if  all lead to win, it loses
    if (vis[v]) return;
    int cntlose = 0;
    int a = 0, b = 0;
    for (auto& x : adj[v]) {
        if (x == p) continue;
        dfs2(x, v);
        if (win2[x]) a += cnt2[x];
        else b += cnt2[x];
        cntlose += !win2[x];
    }
    // cout << "a" << cntlose << "," << v << "," << a << "," << b << endl;
    if (cntlose == 1) {
        cnt2[v] = b;
    }
    if (cntlose == 0) {
        cnt2[v] = a + 1;
    }
    win2[v] = cntlose ? 1 : 0;
}

void cd(int v) {
    dfs(v, -1);
    int N = sz[v];
    int p = v;
    bool cont = 1;
    while (cont) {
        cont = 0;
        for (auto& x : adj[v]) {
            if (sz[x] >= N / 2 && !vis[x] && x != p) {
                p = v; v = x;
                cont = 1;
                break;
            }
        }
    }
    cnt2[v] = 0, win2[v] = 0;
    vis[v] = 1;
    int cntlose = 0, a = 0, b = 0;
    for (auto& x : adj[v]) {
        dfs2(x, v);
        if (win2[x]) a += cnt2[x];
        else b += cnt2[x];
        cntlose += !win2[x];
    }

    for (auto& x : adj[v]) {
        if (vis[x]) continue;
        dfs2(x, v);
        if (win2[x]) a -= cnt2[x];
        else b -= cnt2[x];
        cntlose -= !win2[x];

        // cout << v << "," << cntlose << "," << a << "," << b << endl;
        cnt2[v] = 0;
        if (cntlose == 1) {
            cnt2[v] = b;
        }
        if (cntlose == 0) {
            cnt2[v] = a + 1;
        }
        win2[v] = cntlose ? 1 : 0;

        cd(x);

        dfs2(x, v);
        if (win2[x]) a += cnt2[x];
        else b += cnt2[x];
        cntlose += !win2[x];
    }
    // cout << "fin: " << v << "," << cntlose << "," << a << "," << b << endl;


    cnt[v] = 0;
    if (cntlose == 1) {
        cnt[v] = b;
    }
    if (cntlose == 0) {
        cnt[v] = a + 1;
    }
    win[v] = cntlose ? 1 : 0;
    vis[v] = 0;
}

const int mod = 1e9 + 7;

struct uwu {
    int a = 0, b = 0, c = 0, d = 0;
};

uwu combine(uwu a, uwu b) {
    uwu res;
    res.a = a.a * b.a + a.c * b.c % mod;
    res.b = a.a * b.b + a.c * b.d + a.b * (b.a + b.b + b.c + b.d) % mod;
    res.c = a.c * b.a + a.a * b.c % mod;
    res.d = a.c * b.b + a.a * b.d + a.d * (b.a + b.b + b.c + b.d) % mod;
    return res;
}

uwu binpow(uwu a, int b) {
    if (b == 1) return a;
    uwu c = binpow(combine(a, a), b / 2);
    if (b & 1) c = combine(c, a);
    return c;
}

void solve() {
    int N, D; cin >> N >> D;
    for (int i = 0; i < N - 1; i++) {
        int a, b; cin >> a >> b; a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cd(0);
    int cntw = 0, cntl = 0;
    uwu x;
    for (int i = 0; i < N; i++) {
        if (win[i]) {
            cntw++;
            x.a += cnt[i];
            x.b += N - cnt[i];
        } else {
            cntl++;
            x.c += cnt[i];
            x.d += N - cnt[i];
        }
    }
    x = binpow(x, D);

    if (D == 0) {
        cout << win[0] << endl;
    } else if (D == 1) {
        uwu v;

        if (win[0]) {
            v.a += cnt[0];
            v.b += N - cnt[0];
        } else {
            v.c += cnt[0];
            v.d += N - cnt[0];
        }
        //     cout << v.c << "," << cntl << endl;
        cout << (v.a * cntw + v.b * N + v.c * cntl) % mod << endl;
    } else {

        uwu v;

        if (win[0]) {
            v.a += cnt[0];
            v.b += N - cnt[0];
        } else {
            v.c += cnt[0];
            v.d += N - cnt[0];
        }
        v = combine(v, binpow(x, D - 1));
        cout << (v.a * cntw + v.b * N + v.c * cntl) % mod << endl;
    }
}

int32_t main() {
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

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