Submission #289501

#	Time	Username	Problem	Language	Result	Execution time	Memory
289501		model_code	Star Trek (CEOI20_startrek)	C++17	100 / 100	117 ms	13880 KiB

startrek

#include <iostream>
#include <vector>

using namespace std;

/*
Note that this is an O(N+logD) solution

Made for you by Mate Busa
*/

const long long mod = 1000000007;
long long N, D, a, b, L, W, LC, WC, sL, sW, sLC, sWC;
vector<int> neighbour[100000];
bool lose[100000];
bool visited[100000];
long long c[100000];
long long oW[100000];
long long oL[100000];
long long h[100000];

//calculate the state for all roots
void dfs(int x){
    visited[x] = true; lose[x] = true;
    for(int i:neighbour[x]){
        if(!visited[i]){
            dfs(i);
            if(lose[i]) h[x]++;
        }
    }
    if(h[x]!=0) lose[x] = false;
}
void critical(int x){
    if(lose[x]){
        c[x] = oW[x] + 1;
    } else {
        if(h[x]==1){
            c[x] = oL[x];
        } else {
            c[x] = 0;
        }
    }
}
//calculate critical states
void dfs2(int x){
    visited[x] = true;
    for(int i:neighbour[x]){
        if(!visited[i]){
            dfs2(i);
            if(lose[i]){
                oL[x] += c[i];
            } else {
                oW[x] += c[i];
            }
        }
    }
    critical(x);
}
//reroot the tree in a neighbour
void reroot(int x, int y){
    if(lose[y]){
        h[x]--; oL[x] -= c[y];
    } else {
        oW[x] -= c[y];
    }
    if(h[x]==0) lose[x] = true;
    critical(x);
    if(lose[x]){
        h[y]++; oL[y] += c[x];
    } else {
        oW[y] += c[x];
    }
    if(h[y]!=0) lose[y] = false;
    critical(y);
}
void evaluate(int x){
    visited[x] = true;
    if(lose[x]){
        L++; LC = (LC+c[x])%mod;
    } else {
        W++; WC = (WC+c[x])%mod;
    }
    for(int i:neighbour[x]){
        if(!visited[i]){
            reroot(x,i);
            evaluate(i);
            reroot(i,x);
        }
    }
}

//a bonus dimension
void step(long long pl, long long plc, long long pw, long long pwc){
    sL = ((((pl * N) % mod) * W) % mod + (pwc * L) % mod + ((((pl * N)%mod - plc + mod)%mod) * L)%mod) % mod;
    sLC = (plc * WC + pwc * LC) % mod;
    sW = ((((pw * N) % mod) * W) % mod + (plc * L) % mod + ((((pw * N)%mod - pwc + mod)%mod) * L)%mod) % mod;
    sWC = (pwc * WC + plc * LC) % mod;
}
//double up the number of dimensions
void step2(long long pl, long long plc, long long pw, long long pwc){
    L = ((((pl * N) % mod) * pw) % mod + (pwc * pl) % mod + ((((pl * N)%mod - plc + mod)%mod) * pl)%mod) % mod;
    LC = (plc * pwc + pwc * plc) % mod;
    W = ((((pw * N) % mod) * pw) % mod + (plc * pl) % mod + ((((pw * N)%mod - pwc + mod)%mod) * pl)%mod) % mod;
    WC = (pwc * pwc + plc * plc) % mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> D;
    for(int i=0; i<N-1; i++){
        cin >> a >> b;
        neighbour[a-1].push_back(b-1);
        neighbour[b-1].push_back(a-1);
    }

    dfs(0);
    for(int i=0; i<N; i++) visited[i] = false;
    dfs2(0);
    for(int i=0; i<N; i++) visited[i] = false;
    evaluate(0);

    if(lose[0]){
        sL = 1; sLC = c[0];
    } else {
        sW = 1; sWC = c[0];
    }

    //use binary representation of D
    while(D>0){
        if(D%2==1) step(sL, sLC, sW, sWC);
        step2(L,LC,W,WC); D /= 2;
    }

    cout << sW << '\n';

    return 0;
}

• 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