Submission #1245703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245703		loctildore	Star Trek (CEOI20_startrek)	C++20	50 / 100	1100 ms	80280 KiB

startrek

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
// trans rights
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
#define MOD 1000000007
 
int expn(int x, int y) {
    if (y == 0) return 1;
    int t = expn(x, y / 2);
    t = (t * t) % MOD;
    if (y % 2) t = (t * x) % MOD;
    return t;
}
 
int n, d, lval, eval;
vector<int> grph[100007];
 
int isl[100007];
gp_hash_table<int, int> cdfs[100007], cdfs2[100007];
pair<int, int> lst[100007];
int dfs(int x, int par = -1) {
    if (cdfs[x].find(par) != cdfs[x].end()) {
        return cdfs[x][par];
    }
    int cnt = 0;
    if (lst[x] == make_pair(-1ll, -1ll)) {
        for (int i : grph[x]) if (i != par) cnt += dfs(i, x);
    }
    else {
        cnt = lst[x].s;
        if (~lst[x].f) cnt += dfs(lst[x].f, x);
        if (~par) cnt -= dfs(par, x);
    }
    lst[x] = {par, cnt};
    return cdfs[x][par] = (cnt == 0);
}
int dfs2(int x, int par = -1) {
    if (cdfs2[x].find(par) != cdfs2[x].end()) {
        return cdfs2[x][par];
    }
    int cnt = 0;
    if (lst[x] == make_pair(-1ll, -1ll)) {
        if (cdfs[x][par]) {
            cnt = 1;
            for (int i : grph[x]) if (i != par) {
                if (!cdfs[i][x]) cnt += dfs2(i, x);
            }
        }
        else {
            for (int i : grph[x]) if (i != par) {
                if (cdfs[i][x]) cnt += 1000000 + dfs2(i, x);
            }
        }
    }
    else {
        cnt = lst[x].s;
        if (cdfs[x][par]) {
            if (~lst[x].f) if (!cdfs[lst[x].f][x]) cnt += dfs2(lst[x].f, x);
            if (~par) if (!cdfs[par][x]) cnt -= dfs2(par, x);
        }
        else {
            if (~lst[x].f) if (cdfs[lst[x].f][x]) cnt += 1000000 + dfs2(lst[x].f, x);
            if (~par) if (cdfs[par][x]) cnt -= 1000000 + dfs2(par, x);
        }
    }
    if (cdfs[x][par]) {
        return cdfs2[x][par] = cnt;
    }
    if (cnt / 1000000 == 1) return cdfs2[x][par] = cnt - 1000000;
    return cdfs2[x][par] = 0;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>d;
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin>>a>>b; a--;b--;
        grph[a].push_back(b);
        grph[b].push_back(a);
    }
    for (int i = 0; i < n; i++) lst[i] = {-1, -1};
    for (int i = 0; i < n; i++) {
        lval += (isl[i] = dfs(i));
    }
    for (int i = 0; i < n; i++) lst[i] = {-1, -1};
    for (int i = 0; i < n; i++) {
        if (isl[i]) eval -= dfs2(i);
        else eval += dfs2(i);
    }
    int t1 = (expn(n, 2 * d) - expn(eval, d) + MOD) % MOD;
    int t2 = expn((expn(n, 2) - eval + MOD) % MOD, MOD - 2);
    int t3 = (t1 * t2) % MOD;
    t3 = (lval * t3) % MOD;
    int ans = (cdfs2[0][-1] * t3) % MOD;
    if (!isl[0]) ans = (expn(n, 2 * d) - ans + MOD) % MOD;
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 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