oj.uz

Submission #342938

# Submission time Handle Problem Language Result Execution time Memory
342938 2021-01-03T08:50:07 Z sealnot123 Star Trek (CEOI20_startrek) C++14
45 / 100
 135 ms 17260 KB 
/*
	Author: AquaBlaze
	Time: 2021-01-03 13:25:24
	Generated by powerful Codeforces Tool :^)
 	You can download the binary file in here https://github.com/xalanq/cf-tool (Windows, macOS, Linux)	
    Keqing best girl :)
    Nephren will always be in my heart
*/
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())
#define pc(x) putchar(x)
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long i64;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 100005;
const int mod = 1000000007;

int add(int a, int b){ return ((a+=b)>=mod)?a-mod:a; }
void adding(int &a, int b){ a = add(a, b); }
int mul(int a, int b){ return a*1ll*b%mod; }

pii operator + (const pii& A, const pii& B){
    return pii(add(A.x,B.x), add(A.y,B.y));
}
pii operator - (const pii& A, const pii& B){
    return pii(add(A.x,mod-B.x), add(A.y,mod-B.y));
}

vector<int> g[N];
int result[N], final_res[N];
pii dp[N][2], final_dp[N][2];

void add_node(int u, int v){
    result[u] -= !result[v];
    if(result[u]){
        dp[u][1] = dp[u][1]+dp[v][0]+dp[v][1];
    }else{
        dp[u][0] = dp[u][0]+dp[v][1];
        dp[u][1] = dp[u][1]+dp[v][0];
    }
    result[u] += !result[v];
}

void sub_node(int u, int v){
    result[u] -= !result[v];
    if(result[u]){
        dp[u][1] = dp[u][1]-(dp[v][0]+dp[v][1]);
    }else{
        dp[u][0] = dp[u][0]-dp[v][1];
        dp[u][1] = dp[u][1]-dp[v][0];
    }
    result[u] += !result[v];
}

void adjust(int u){
    if(!result[u]){
        dp[u][0] = dp[u][0]+pii(1, 0);
        dp[u][1] = dp[u][1]+pii(0, 1);
    }else dp[u][1] = dp[u][1]+pii(1, 1);
}

void dejust(int u){
    if(!result[u]){
        dp[u][0] = dp[u][0]-pii(1, 0);
        dp[u][1] = dp[u][1]-pii(0, 1);
    }else dp[u][1] = dp[u][1]-pii(1, 1);
}

void dfs(int u, int p){
    for(int &e : g[u]){
        if(e == p){
            swap(e, g[u].back());
            g[u].pop_back();
            break;
        }
    }
    for(const int &e : g[u]){
        dfs(e, u);
        result[u] += (!result[e]);
    }
    adjust(u);
    for(const int &e : g[u]){
        add_node(u, e);
    }
}

void tour(int u){
    final_res[u] = !(!result[u]);
    FOR(i, 0, 1) final_dp[u][i] = dp[u][i];
    for(const int &e : g[u]){
        sub_node(u, e);
        dejust(u);
        result[u] -= !result[e];
        adjust(u);
        dejust(e);
        result[e] += !result[u];
        adjust(e);
        add_node(e, u);

        tour(e);

        sub_node(e, u);
        dejust(e);
        result[e] -= !result[u];
        adjust(e);
        dejust(u);
        result[u] += !result[e];
        adjust(u);
        add_node(u, e);
    }
}

vvi pw[60];

void solve(){
    int n;
    i64 d;
    cin >> n >> d;
    FOR(i, 2, n){
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
        g[b].eb(a);
    }
    /*
    i64 a = 1, r = 4;
    for(i64 i = 1; i <= d; i<<=1,r=mul(r,r)){
        if(i&d) a=mul(a,r);
    }
    printf("%lld",a);
    return ;
    */
    dfs(1, -1);
    tour(1);
    pii p = final_dp[1][1];
    pw[0].resize(2,vi(2, 0));
    FOR(i, 1, n){
        FOR(j, 0, 1){
            adding(pw[0][j^1][0], final_dp[i][j].x);
            adding(pw[0][j^1][1], final_dp[i][j].y);
        }
    }
    /*
    FOR(i, 1, n){
        printf("[%d]\n",i);
        FOR(j, 0, 1){
            printf("%d %d\n",dp[i][j].x,dp[i][j].y);
        }
    }
    */
    FOR(t, 1, 59){
        pw[t].resize(2, vi(2, 0));
        FOR(i, 0, 1){
            FOR(j, 0, 1){
                FOR(k, 0, 1){
                    adding(pw[t][i][j], mul(pw[t-1][i][k],pw[t-1][k][j]));
                }
            }
        }
    }
    vi res(2,0);
    FOR(i, 1, n) res[1-final_res[i]]++;
    --d;
    FOR(t, 0, 59){
        if(d&(1ll<<t)){
            vi tmp(2,0);
            FOR(i, 0, 1){
                FOR(j, 0, 1){
                    adding(tmp[i], mul(res[j],pw[t][i][j]));
                }
            }
            res = tmp;
        }
    }
    int ans = add(mul(p.x,res[0]),mul(p.y,res[1]));
    printf("%d",ans);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Incorrect 3 ms 2796 KB Output isn't correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2756 KB Output is correct
11 Correct 2 ms 2796 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2756 KB Output is correct
11 Correct 2 ms 2796 KB Output is correct
12 Correct 99 ms 13804 KB Output is correct
13 Correct 114 ms 17260 KB Output is correct
14 Correct 85 ms 10856 KB Output is correct
15 Correct 135 ms 10988 KB Output is correct
16 Correct 112 ms 11084 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2756 KB Output is correct
11 Correct 2 ms 2796 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Incorrect 2 ms 2796 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2756 KB Output is correct
11 Correct 2 ms 2796 KB Output is correct
12 Correct 99 ms 13804 KB Output is correct
13 Correct 114 ms 17260 KB Output is correct
14 Correct 85 ms 10856 KB Output is correct
15 Correct 135 ms 10988 KB Output is correct
16 Correct 112 ms 11084 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Incorrect 2 ms 2796 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Incorrect 3 ms 2796 KB Output isn't correct