oj.uz

Submission #577763

# Submission time Handle Problem Language Result Execution time Memory
577763 2022-06-15T08:43:52 Z talant117408 Star Trek (CEOI20_startrek) C++17
45 / 100
 132 ms 15180 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int mod = 1e9+7;

ll add(ll a, ll b) {
    return ((a + b) % mod + mod) % mod;
}

ll mult(ll a, ll b) {
    return ((a * b) % mod + mod) % mod;
}

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 1e5+7;
vector <int> graph[N];
int state[N], state_root[N], losing_children[N], parent[N], life_changing[N];
int losing[N], winning[N];

int dfs(int v, int p) {
    parent[v] = p;
    int l = 0;
    for (auto to : graph[v]) {
        if (to == parent[v]) {
            continue;
        }
        l += dfs(to, v);
    }
    losing_children[v] = l;
    state[v] = 1 - (losing_children[v] > 0);
    return state[v];
}

void dfs2(int v, int i) {
    state_root[v] = state[v];
    (state[v] ? losing[i] : winning[i])++;
    for (auto to : graph[v]) {
        if (to == parent[v]) {
            continue;
        }
        if (state[to] && !state[v] && !state[parent[v]] && losing_children[v] == 1) {
            losing_children[v]--;
            losing_children[to]++;
            state[v] = 1;
            state[to] = 0;
            dfs2(to, i);
            losing_children[v]++;
            losing_children[to]--;
            state[v] = 0;
            state[to] = 1;
        }
        else {
            dfs2(to, i);
        }
    }
}

void dfs3(int v, int i) {
    if (v != parent[v] && state[v] == state[parent[v]]) {
        return;
    }
    if (!state[v] && losing_children[v] > 1) {
        return;
    }
    if (state[v]) {
        life_changing[i]++;
    }
    for (auto to : graph[v]) {
        if (to == parent[v]) {
            continue;
        }
        dfs3(to, i);
    }
}

void solve() {
    int n;
    ll D;
    cin >> n >> D;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    if (D <= 1e5) {
        ll all_life_changing = 0;
        dfs(1, 1);
        dfs2(1, D);
        dfs3(1, 1);
        if (D > 1) {
            for (int i = 1; i <= n; i++) {
                dfs(i, i);
                dfs3(i, i);
                all_life_changing = add(all_life_changing, (state_root[i] ? 1 : -1) * life_changing[i]);
            }
            for (int j = D-1; j >= 1; j--) {
                losing[j] = add(losing[j], mult(add(mult(n, n), -all_life_changing), losing[j+1])); 
                winning[j] = add(mult(n, binpow(n, (D-j)*2)), -losing[j]);
            }
        }
        if (state_root[1]) {
            cout << mult(life_changing[1], losing[1]) << endl;
        }
        else {
            cout << add(mult(n, winning[1]), mult(n-life_changing[1], losing[1])) << endl;
        }
    }
    else if (n == 2) {
        cout << binpow(n, D*2);
    }
}

int main() {
    //~ do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
13 1
1 2
1 3
1 4
1 5
5 6
1 12
12 13
1 7
7 8
8 11
8 9
10 9
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 14 ms 2732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 113 ms 10832 KB Output is correct
13 Correct 123 ms 15180 KB Output is correct
14 Correct 96 ms 7512 KB Output is correct
15 Correct 132 ms 7276 KB Output is correct
16 Correct 99 ms 7360 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 14 ms 2644 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 113 ms 10832 KB Output is correct
13 Correct 123 ms 15180 KB Output is correct
14 Correct 96 ms 7512 KB Output is correct
15 Correct 132 ms 7276 KB Output is correct
16 Correct 99 ms 7360 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Incorrect 14 ms 2644 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 14 ms 2732 KB Output isn't correct
3 Halted 0 ms 0 KB -