oj.uz

Submission #342941

# Submission time Handle Problem Language Result Execution time Memory
342941 2021-01-03T08:53:21 Z sealnot123 Star Trek (CEOI20_startrek) C++14
45 / 100
 114 ms 15980 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);
    }
    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 2 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 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 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 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 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 2816 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 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 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 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 2816 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 100 ms 12652 KB Output is correct
13 Correct 114 ms 15980 KB Output is correct
14 Correct 84 ms 10108 KB Output is correct
15 Correct 97 ms 9836 KB Output is correct
16 Correct 107 ms 9856 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 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 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 2816 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 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 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 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 2816 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 2 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 100 ms 12652 KB Output is correct
13 Correct 114 ms 15980 KB Output is correct
14 Correct 84 ms 10108 KB Output is correct
15 Correct 97 ms 9836 KB Output is correct
16 Correct 107 ms 9856 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 2 ms 2796 KB Output isn't correct