oj.uz

Submission #659642

# Submission time Handle Problem Language Result Execution time Memory
659642 2022-11-18T20:48:32 Z Lobo Star Trek (CEOI20_startrek) C++17
23 / 100
 1000 ms 98700 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 5e5+10;
const int mod = 1e9+7;

int n, d, dpw[maxn][2], dpl[maxn][2], dpwup[maxn][2], dplup[maxn][2];
vector<int> g[maxn];
int SL, SW, SL0, SW0, SWb, SLb;

void dfs1(int u, int ant) {
    dpw[u][1] = SW*dpw[u][0] + SL*(dpw[u][0]+dpl[u][0]); dpw[u][1]%= mod;
    dpl[u][1] = SW*dpl[u][0]; dpl[u][1]%= mod;

    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        qtl+= dpl[v][0];
        dfs1(v,u);
    }

    for(auto v : g[u]) if(v != ant) {
        qtl-= dpl[v][0];
        if(qtl) {
            dpw[u][1]+= dpw[v][1]+dpl[v][1]; dpw[u][1]%= mod;
            dpl[u][1]+= 0;
        }
        else {
            dpw[u][1]+= dpl[v][1]; dpw[u][1]%= mod;
            dpl[u][1]+= dpw[v][1]; dpl[u][1]%= mod;
        }
        qtl+= dpl[v][0];
    }
}

map<int,int> wp[maxn];
int solwp(int u, int ant) {
    if(wp[u].count(ant)) return wp[u][ant];
    wp[u][ant] = 0;
    for(auto v : g[u]) if(v != ant) {
        if(solwp(v,u) == 0) wp[u][ant] = 1;
    }
    return wp[u][ant];
}

// void dfs0(int u, int ant) {
//     dpw[u][0] = 0;
//     for(auto v : g[u]) if(v != ant) {
//         dfs0(v,u);
//     }
//     for(auto v : g[u]) if(v != ant) {
//         if(solwp(v,u) == 0) dpw[u][0] = 1;
//     }
//     dpl[u][0] = 1-dpw[u][0];
// }

int dw[maxn][2], dl[maxn][2], sdw[maxn][2], sdl[maxn][2], sbsz[maxn];
vector<int> dl0s[maxn];
void sol(int u, int ant) {
    dw[u][0] = 0;
    dl[u][0] = 0;
    sdw[u][0] = 0;
    sdl[u][0] = 0;
    dw[u][1] = 0;
    dl[u][1] = 0;
    sdw[u][1] = 0;
    sdl[u][1] = 0;
    sbsz[u] = 1;
    for(auto v : g[u]) if(v != ant) {
        sol(v,u);
        sdw[u][0]+= dw[v][0];
        sdw[u][1]+= dw[v][1];
        sdl[u][0]+= dl[v][0];
        sdl[u][1]+= dl[v][1];
        sbsz[u]+= sbsz[v];
        if(dl[v][0]) {
            dl0s[u].pb(v);
        }
    }

    if(sdl[u][0] >= 1) {
        dw[u][0] = 1;
    }
    else {
        dw[u][0] = 0;
    }

    if(sdl[u][0] >= 2) {
        dw[u][1] = 1+sdw[u][1]+sdl[u][1];
    }
    else if(sdl[u][0] == 1) {
        dw[u][1] = 1+sdw[u][1]+sdl[u][1];
        int v1 = dl0s[u][0];
        dw[u][1]-= dw[v1][1];
    }
    else {
        dw[u][1] = 1+sdl[u][1];
    }
    dl[u][0] = 1-dw[u][0];
    dl[u][1] = sbsz[u]-dw[u][1];
}

void dfs0(int u, int ant) {
    dpw[u][0] = 0;
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        dfs0(v,u);
        qtl+= dpl[v][0];
    }

    if(qtl) dpw[u][0] = 1;
    dpl[u][0] = 1-dpw[u][0];
}

void dfs0up(int u, int ant) {
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        qtl+= dpl[v][0];
    }

    for(auto v : g[u]) if(v != ant) {
        qtl-= dpl[v][0];
        if(qtl || dpwup[u][0]) {
            dpwup[v][0] = 0;
            dplup[v][0] = 1-dpwup[v][0];
        }
        else {
            dpwup[v][0] = 1;
            dplup[v][0] = 1-dpwup[v][0];
        }
        qtl+= dpl[v][0];
    }

    for(auto v : g[u]) if(v != ant) {
        dfs0up(v,u);
    }
}

int dpwc[maxn], dplc[maxn], dpwupc[maxn], dplupc[maxn];
void dfscnt(int u, int ant, int b) {
    dpwc[u] = 0;
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        dfscnt(v,u,b);
        qtl+= dplc[v];
    }

    if(qtl || u == b) dpwc[u] = 1;
    dplc[u] = 1-dpwc[u];
}

void dfscntup(int u, int ant, int b) {
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        qtl+= dplc[v];
    }

    for(auto v : g[u]) if(v != ant) {
        qtl-= dplc[v];
        if((qtl || dpwupc[u]) && v != b) {
            dpwupc[v] = 0;
            dplupc[v] = 1-dpwupc[v];
        }
        else {
            dpwupc[v] = 1;
            dplupc[v] = 1-dpwupc[v];
        }
        qtl+= dplc[v];
    }

    for(auto v : g[u]) if(v != ant) {
        dfscntup(v,u,b);
    }
}
void solve() {
    cin >> n >> d;

    for(int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs0(1,0);
    dpwup[1][0] = 0;
    dplup[1][0] = 1;
    dfs0up(1,0);
    for(int i = 1; i <= n; i++) {
        if(dpw[i][0] || dpwup[i][0]) SW0++;
        else SL0++;
    }

    for(int i = 1; i <= n; i++) {
        // dfscnt(1,0,i);
        // if(i == 1) {
        //     dpwupc[1] = 1;
        //     dplupc[1] = 0;
        // }
        // else {
        //     dpwupc[1] = 0;
        //     dplupc[1] = 1;
        // }
        // dfscntup(1,0,i);
        // for(int j = 1; j <= n; j++) {
        //     // cout << i << " " << j << " " << (dpwc[j] || dpwupc[j]) << endl;
        //     if(dpwc[j] || dpwupc[j]) SWb++;
        // }

        sol(i,0);
        SWb+= dw[i][1];
    }
    SLb = n*n-SWb;

    // cout << SWb << " " << SLb << endl;
    // cout << SW0 << " " << SL0 << endl;
    SWb%= mod;
    SLb%= mod;
    SW = SW0;
    SL = SL0;
    for(int i = 1; i <= d-1; i++) {
        int newSW = n*(SW*SW0%mod)%mod + SL*SWb; newSW%= mod;
        int newSL = n*(SW*SL0%mod)%mod + SL*SLb; newSL%= mod;
        SW = newSW;
        SL = newSL;
    }
    dfs1(1,0);
    // cout << SW << " " << SL << endl;
    cout << dpw[1][1] << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47244 KB Output is correct
2 Correct 22 ms 47364 KB Output is correct
3 Execution timed out 1098 ms 47316 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 22 ms 47376 KB Output is correct
3 Correct 24 ms 47408 KB Output is correct
4 Correct 26 ms 47444 KB Output is correct
5 Correct 23 ms 47348 KB Output is correct
6 Correct 22 ms 47328 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 22 ms 47376 KB Output is correct
3 Correct 24 ms 47408 KB Output is correct
4 Correct 26 ms 47444 KB Output is correct
5 Correct 23 ms 47348 KB Output is correct
6 Correct 22 ms 47328 KB Output is correct
7 Correct 47 ms 52248 KB Output is correct
8 Correct 55 ms 53360 KB Output is correct
9 Correct 45 ms 51724 KB Output is correct
10 Correct 47 ms 52404 KB Output is correct
11 Correct 48 ms 51940 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 22 ms 47376 KB Output is correct
3 Correct 24 ms 47408 KB Output is correct
4 Correct 26 ms 47444 KB Output is correct
5 Correct 23 ms 47348 KB Output is correct
6 Correct 22 ms 47328 KB Output is correct
7 Correct 47 ms 52248 KB Output is correct
8 Correct 55 ms 53360 KB Output is correct
9 Correct 45 ms 51724 KB Output is correct
10 Correct 47 ms 52404 KB Output is correct
11 Correct 48 ms 51940 KB Output is correct
12 Execution timed out 1093 ms 98700 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 22 ms 47376 KB Output is correct
3 Correct 24 ms 47408 KB Output is correct
4 Correct 26 ms 47444 KB Output is correct
5 Correct 23 ms 47348 KB Output is correct
6 Correct 22 ms 47328 KB Output is correct
7 Correct 47 ms 52248 KB Output is correct
8 Correct 55 ms 53360 KB Output is correct
9 Correct 45 ms 51724 KB Output is correct
10 Correct 47 ms 52404 KB Output is correct
11 Correct 48 ms 51940 KB Output is correct
12 Correct 24 ms 47316 KB Output is correct
13 Incorrect 47 ms 52780 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 22 ms 47376 KB Output is correct
3 Correct 24 ms 47408 KB Output is correct
4 Correct 26 ms 47444 KB Output is correct
5 Correct 23 ms 47348 KB Output is correct
6 Correct 22 ms 47328 KB Output is correct
7 Correct 47 ms 52248 KB Output is correct
8 Correct 55 ms 53360 KB Output is correct
9 Correct 45 ms 51724 KB Output is correct
10 Correct 47 ms 52404 KB Output is correct
11 Correct 48 ms 51940 KB Output is correct
12 Execution timed out 1093 ms 98700 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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