oj.uz

Submission #975319

# Submission time Handle Problem Language Result Execution time Memory
975319 2024-05-04T18:46:52 Z efedmrlr Star Trek (CEOI20_startrek) C++17
45 / 100
 50 ms 15644 KB 
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;
const int B = 2;
int add(int x, int y) {
    if(x + y >= MOD) return x + y - MOD;
    return x + y;
}
int mult(int x, int y) {
    return (int)((1ll * x * y) % MOD);
}
int subt(int x, int y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
int fp(int x, lli y) {
    int ret = 1;
    while(y > 0ll) {
        if(y & 1ll) {
            ret = mult(ret, x);
        }
        x = mult(x, x);
        y /= 2ll;
    }
    return ret;
}

struct Matrix {
    array<array<int, B>, B> mat;
    Matrix() {
        REP(i, B) REP(j, B) mat[i][j] = 0;
    }
};
Matrix mult(Matrix x, Matrix y) {
    Matrix ret;
    REP(i, 2) REP(j, 2) REP(k, 2) {
        ret.mat[i][j] = add(ret.mat[i][j], mult(x.mat[i][k], y.mat[k][j]));
    }
    return ret;
}
Matrix fp(Matrix x, lli y) {
    Matrix ret;
    REP(i, B) ret.mat[i][i] = 1;
    while(y > 0ll) {
        if(y & 1) {
            ret = mult(ret, x);
        }
        y /= 2ll;
        x = mult(x, x);
    }
    return ret;
}
int n;
lli d;
vector<vector<int> > adj(N, vector<int>());
vector<int> dp(N, 0), dpr(N, 0);
vector<int> dpcrit(N, 0), dpc(N, 0);
vector<int> wc(N, 0), lc(N, 0);
int L = 0;
int CL = 0, CW = 0;
void dfs1(int node, int par) {
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfs1(c, node);
        if(!dpr[c]) dpr[node]++;
    }

}
void dfs2(int node, int par) {
    if(!dpr[node]) {
        dpcrit[node] = 1;
    }
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfs2(c, node);
        if(dpr[c]) wc[node] += dpcrit[c];
        else lc[node] += dpcrit[c];
        if(dpr[node] == 1 && !dpr[c]) {
            dpcrit[node] += dpcrit[c];
        } 
        if(!dpr[node] && dpr[c]) {
            dpcrit[node] += dpcrit[c];
        }
    }
    
}
void change_root(int p, int x) {
    if(!dpr[x]) {
        dpr[p]--;
        lc[p] -= dpcrit[x];
    }
    else {
        wc[p] -= dpcrit[x];
    }
    if(dpr[p] >= 2) {
        dpcrit[p] = 0;
    }
    else if(dpr[p] == 1) {
        dpcrit[p] = lc[p];
    }
    else {
        dpcrit[p] = wc[p] + 1;
    }

    if(!dpr[p]) {
        dpr[x]++;
        lc[x] += dpcrit[p];
    }
    else {
        wc[x] += dpcrit[p];
    }
    if(dpr[x] >= 2) {
        dpcrit[x] = 0;
    }
    else if(dpr[x] == 1) {
        dpcrit[x] = lc[x];
    }
    else {
        dpcrit[x] = wc[x] + 1;
    }

}

void reroot(int node, int par) {
    dp[node] = dpr[node];
    dpc[node] = dpcrit[node];
    for(auto c : adj[node]) {
        if(c == par) continue;
        change_root(node, c);
        reroot(c, node);
        change_root(c, node); 
    }

}

void solve() {
    cin >> n >> d;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << " dpr:" << dpr[i] << " crit:" << dpcrit[i] << "\n";
    // }
    reroot(1, 0);
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << " dp:" << dp[i] << " c:" << dpc[i] << "\n";
    // }
    for(int i = 1; i <= n; i++) {
        if(!dp[i]) {
            L++;
            CL = add(CL, dpc[i]);
        }
        else {
            CW = add(CW, dpc[i]);
        }
    }
    // cout << "L:" << L << " CL:" << CL << " CW:" << CW << "\n";
    // int LD = L, LDN = 0;
    // for(int i = 1; i < d; i++) {
    //     LDN = add(mult(LD, subt(CW, CL)), mult(L, fp(n, 2ll * i)));
    //     swap(LD, LDN);
    // }
    Matrix rel;
    rel.mat[0] = {subt(CW, CL), 1};
    rel.mat[1] = {0, mult(n, n)};
    Matrix st;
    st.mat[0][0] = L;
    st.mat[1][1] = mult(L, mult(n, n));
    st = mult(st, fp(rel, d - 1));
    int ans = 0;
    if(dp[1]) {
        ans = mult(dpc[1], st.mat[0][0]);
    }
    else {
        ans = subt(fp(n, 2ll * d), mult(dpc[1], st.mat[0][0]));
    }
    ans = subt(fp(n, 2ll * d), ans);
    cout << ans << "\n";
}

signed main() {
    fastio();
    solve();
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5172 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5176 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5176 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5176 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 50 ms 12136 KB Output is correct
13 Correct 45 ms 15644 KB Output is correct
14 Correct 29 ms 9432 KB Output is correct
15 Correct 36 ms 9464 KB Output is correct
16 Correct 37 ms 9304 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5176 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 2 ms 4952 KB Output is correct
13 Incorrect 3 ms 5212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5176 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 50 ms 12136 KB Output is correct
13 Correct 45 ms 15644 KB Output is correct
14 Correct 29 ms 9432 KB Output is correct
15 Correct 36 ms 9464 KB Output is correct
16 Correct 37 ms 9304 KB Output is correct
17 Correct 2 ms 4952 KB Output is correct
18 Incorrect 3 ms 5212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -