oj.uz

Submission #342961

# Submission time Handle Problem Language Result Execution time Memory
342961 2021-01-03T09:23:03 Z sealnot123 Star Trek (CEOI20_startrek) C++14
43 / 100
 1000 ms 492 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 = 1005;
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];
pii 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 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 dfs(int u, int p){
    for(const int &e : g[u]){
        if(e == p) continue;
        dfs(e, u);
        result[u] += (!result[e]);
    }
    adjust(u);
    for(const int &e : g[u]){
        if(e == p) continue;
        add_node(u, e);
    }
}

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);
    }
    vvi m(2, vi(2,0));
    vi res(2, 0);
    ROF(i, n, 1){
        memset(dp, 0, sizeof dp);
        memset(result, 0, sizeof result);
        dfs(i, -1);
        int r = !(!result[i]);
        res[1-r]++;
        FOR(j, 0, 1){
            adding(m[j^1][0], dp[i][j].x);
            adding(m[j^1][1], dp[i][j].y);
        }
    }
    FOR(t, 2, d){
        vi tmp(2, 0);
        FOR(i, 0, 1){
            FOR(j, 0, 1){
                adding(tmp[i], mul(res[j], m[i][j]));
            }
        }
        res = tmp;
    }
    int ans = 0;
    adding(ans, mul(dp[1][1].x, res[0]));
    adding(ans, mul(dp[1][1].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 1 ms 364 KB Output is correct
2 Correct 38 ms 492 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 1096 ms 364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 35 ms 492 KB Output is correct
8 Correct 38 ms 492 KB Output is correct
9 Correct 28 ms 364 KB Output is correct
10 Correct 36 ms 364 KB Output is correct
11 Correct 35 ms 364 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 35 ms 492 KB Output is correct
8 Correct 38 ms 492 KB Output is correct
9 Correct 28 ms 364 KB Output is correct
10 Correct 36 ms 364 KB Output is correct
11 Correct 35 ms 364 KB Output is correct
12 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 35 ms 492 KB Output is correct
8 Correct 38 ms 492 KB Output is correct
9 Correct 28 ms 364 KB Output is correct
10 Correct 36 ms 364 KB Output is correct
11 Correct 35 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 34 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 42 ms 492 KB Output is correct
22 Correct 48 ms 492 KB Output is correct
23 Correct 27 ms 364 KB Output is correct
24 Correct 34 ms 364 KB Output is correct
25 Correct 35 ms 364 KB Output is correct
26 Correct 36 ms 492 KB Output is correct
27 Correct 41 ms 492 KB Output is correct
28 Correct 21 ms 364 KB Output is correct
29 Correct 37 ms 364 KB Output is correct
30 Correct 46 ms 492 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 35 ms 492 KB Output is correct
8 Correct 38 ms 492 KB Output is correct
9 Correct 28 ms 364 KB Output is correct
10 Correct 36 ms 364 KB Output is correct
11 Correct 35 ms 364 KB Output is correct
12 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 38 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Execution timed out 1096 ms 364 KB Time limit exceeded
6 Halted 0 ms 0 KB -