oj.uz

Submission #577752

# Submission time Handle Problem Language Result Execution time Memory
577752 2022-06-15T08:38:13 Z talant117408 Star Trek (CEOI20_startrek) C++17
30 / 100
 1000 ms 13484 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);
        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;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 15 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 1 ms 2644 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 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 2 ms 2644 KB Output is correct
5 Correct 2 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 20 ms 2772 KB Output is correct
8 Correct 26 ms 2804 KB Output is correct
9 Correct 19 ms 2736 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 21 ms 2644 KB Output is correct

Subtask #5
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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 20 ms 2772 KB Output is correct
8 Correct 26 ms 2804 KB Output is correct
9 Correct 19 ms 2736 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 21 ms 2644 KB Output is correct
12 Execution timed out 1079 ms 13484 KB Time limit exceeded
13 Halted 0 ms 0 KB -

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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 20 ms 2772 KB Output is correct
8 Correct 26 ms 2804 KB Output is correct
9 Correct 19 ms 2736 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 21 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 14 ms 2660 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 20 ms 2772 KB Output is correct
8 Correct 26 ms 2804 KB Output is correct
9 Correct 19 ms 2736 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 21 ms 2644 KB Output is correct
12 Execution timed out 1079 ms 13484 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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