Submission #558844

#	Time	Username	Problem	Language	Result	Execution time	Memory
558844		RaresFelix	Star Trek (CEOI20_startrek)	C++17	100 / 100	87 ms	18684 KiB

startrek

#include <bits/stdc++.h>
#define MN 100071
#define MOD 1000000007

using namespace std;
using ll = long long;

ll n, d;
vector<int> L[MN];

ll logp(ll a, ll e) {
    return !e ? 1 : 
        (e & 1) ? a * logp(a * a % MOD, e >> 1) % MOD :
                    logp(a * a % MOD, e >> 1);
}


ll alpha, beta_c, lambda0, state0;
namespace ARB {
    ll NrFiiL[MN], NrC[2][MN];
    ll StateRad[MN], C[MN];
    void dbgTree() {
        for(int i = 1; i <= n; ++i) printf("Nod %d - %d %d %d - %d %d\n", i, NrFiiL[i], NrC[0][i], NrC[1][i], StateRad[i], C[i]);
        printf("--------\n");
    }
    inline bool stare(int u) {
        return !!NrFiiL[u];
    }
    inline ll fnrc(int u) {
        if(NrFiiL[u] > 1) return 0;
        if(NrFiiL[u] == 1) return NrC[0][u];
        return NrC[1][u] + 1;
    }
    void dfs_init(int u, int p) {
        for(auto it : L[u])
            if(it != p) {
                dfs_init(it, u);
                NrFiiL[u] += !stare(it);
            }
        for(auto it : L[u])
            if(it != p) {
                NrC[stare(it)][u] += fnrc(it);
            }
    }
    void move_root(int u, int v) {
        NrFiiL[u] -= !stare(v);
        NrC[stare(v)][u] -= fnrc(v);
        NrC[stare(u)][v] += fnrc(u);
        NrFiiL[v] += !stare(u);
    }
    void dfs_ch_root(int u, int p) {
        //radacina este in u
        C[u] = fnrc(u);
        StateRad[u] = stare(u);
        for(auto it : L[u]) if(it != p) {
            move_root(u, it);
            dfs_ch_root(it, u);
            move_root(it, u);
        }
    }

    void init() {
        dfs_init(1, 0);
        dfs_ch_root(1, 0);
        beta_c = 0;
        for(int i = 1; i <= n; ++i) {
            alpha += (StateRad[i] ? 1 : -1) * C[i];
            alpha = (alpha % MOD + MOD) % MOD;
            beta_c += !StateRad[i];
            lambda0 += !StateRad[i];
        }
        beta_c = beta_c * logp(n, 2 * d);
    }
}

pair<ll, ll> conv(ll a, ll b, ll nr) {
    if(!nr) return {1, 0};
    auto [a1, b1] = conv(a, b, nr >> 1);
    ll a2 = 1ll * a1 * a1 % MOD, b2 = b1 * (a1 + 1) % MOD; 
    if(nr & 1) {
        a1 = a2, b1 = b2;
        a2 = a1 * a, b2 = (b1 * a + b) % MOD;
    }
    return {a2, b2};
}

ll inv(ll a) {
    return logp(a, MOD - 2);
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d;
    for(int i = 1; i < n; ++i) {
        ll u, v;
        cin >> u >> v;
        L[u].push_back(v);
        L[v].push_back(u);
    }
    ARB::init();
    ll lambda_d1 = logp(n, 2 * d) - logp(alpha, d);
    lambda_d1 = (lambda_d1 % MOD + MOD) % MOD;
    ll div = n * n % MOD - alpha;
    div = (div % MOD + MOD) % MOD;
    div = inv(div);
    lambda_d1 = lambda_d1 * div % MOD * lambda0 % MOD;
    ll rez = 0;
    if(ARB::StateRad[1]) rez = ((logp(n, 2 * d) - lambda_d1 * ARB::C[1] % MOD ) % MOD + MOD ) % MOD;
    else rez = lambda_d1 * ARB::C[1] % MOD;
    cout << rez << "\n";
    return 0;
}

Compilation message (stderr)

startrek.cpp: In function 'void ARB::dbgTree()':
startrek.cpp:23:55: warning: format '%d' expects argument of type 'int', but argument 3 has type 'll' {aka 'long long int'} [-Wformat=]
   23 |         for(int i = 1; i <= n; ++i) printf("Nod %d - %d %d %d - %d %d\n", i, NrFiiL[i], NrC[0][i], NrC[1][i], StateRad[i], C[i]);
      |                                                      ~^                      ~~~~~~~~~
      |                                                       |                              |
      |                                                       int                            ll {aka long long int}
      |                                                      %lld
startrek.cpp:23:58: warning: format '%d' expects argument of type 'int', but argument 4 has type 'll' {aka 'long long int'} [-Wformat=]
   23 |         for(int i = 1; i <= n; ++i) printf("Nod %d - %d %d %d - %d %d\n", i, NrFiiL[i], NrC[0][i], NrC[1][i], StateRad[i], C[i]);
      |                                                         ~^                              ~~~~~~~~~
      |                                                          |                                      |
      |                                                          int                                    ll {aka long long int}
      |                                                         %lld
startrek.cpp:23:61: warning: format '%d' expects argument of type 'int', but argument 5 has type 'll' {aka 'long long int'} [-Wformat=]
   23 |         for(int i = 1; i <= n; ++i) printf("Nod %d - %d %d %d - %d %d\n", i, NrFiiL[i], NrC[0][i], NrC[1][i], StateRad[i], C[i]);
      |                                                            ~^                                      ~~~~~~~~~
      |                                                             |                                              |
      |                                                             int                                            ll {aka long long int}
      |                                                            %lld
startrek.cpp:23:66: warning: format '%d' expects argument of type 'int', but argument 6 has type 'll' {aka 'long long int'} [-Wformat=]
   23 |         for(int i = 1; i <= n; ++i) printf("Nod %d - %d %d %d - %d %d\n", i, NrFiiL[i], NrC[0][i], NrC[1][i], StateRad[i], C[i]);
      |                                                                 ~^                                            ~~~~~~~~~~~
      |                                                                  |                                                      |
      |                                                                  int                                                    ll {aka long long int}
      |                                                                 %lld
startrek.cpp:23:69: warning: format '%d' expects argument of type 'int', but argument 7 has type 'll' {aka 'long long int'} [-Wformat=]
   23 |         for(int i = 1; i <= n; ++i) printf("Nod %d - %d %d %d - %d %d\n", i, NrFiiL[i], NrC[0][i], NrC[1][i], StateRad[i], C[i]);
      |                                                                    ~^                                                      ~~~~
      |                                                                     |                                                         |
      |                                                                     int                                                       ll {aka long long int}
      |                                                                    %lld

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