oj.uz

답안 #759867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759867 2023-06-17T01:13:42 Z resting Star Trek (CEOI20_startrek) C++17
15 / 100
 2 ms 2772 KB 
#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];
        }
    }

    cntl %= mod; cntw %= mod; x.a %= mod; x.b %= mod; x.c %= mod; x.d %= mod;

    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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 2 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 2 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 2 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 2 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -