oj.uz

Submission #975108

# Submission time Handle Problem Language Result Execution time Memory
975108 2024-05-04T12:54:15 Z efedmrlr Star Trek (CEOI20_startrek) C++17
45 / 100
 63 ms 17460 KB 
#include <bits/stdc++.h>

#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;

int add(int x, int y) {
    if(x + y >= MOD) return x + y - MOD;
    return x + y;
}
int mult(int x, int y) {
    return (int)((1ll * x * y) % MOD);
}
int subt(int x, int y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
int fp(lli x, lli y) {
    lli ret = 1;
    while(y > 0ll) {
        if(y & 1ll) {
            ret = mult(ret, x);
        }
        x = mult(x, x);
        y /= 2ll;
    }
    return ret;
}
vector<bool> dp(N, 0), dpp(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<bool> dep(N, 0);
vector<int> sub(N, 0);
lli n, d;

void dfsdp(int node, int par) {
    sub[node] = 1;
    for(auto c : adj[node]) {
        if(c == par) continue;
        dep[c] = !dep[node];
        dfsdp(c, node);   
        sub[node] += sub[c];

        if(!dp[c]) dp[node] = 1;
    }

}
void dfsdpp(int node, int par) {
    bool f = 0;
    for(auto c : adj[node]) {
        if(c == par) continue;
        if(!dpp[node]) dpp[c] = 1;
        if(f) dpp[c] = 1;
        if(!dp[c]) f = 1;
    }
    f = 0;
    for(int i = adj[node].size() - 1; i>=0; i--) {
        auto c = adj[node][i];
        if(c == par) continue;
        if(f) dpp[c] = 1;
        if(!dp[c]) f = 1;
    }
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfsdpp(c, node);
    }
}
int ans = 0, win = 0;
void dfswin(int node, int par) {
    int lcnt = 0;
    if(!dep[node]) {
        for(auto c : adj[node]) {
            if(c == par) continue;
            if(!dp[c]) lcnt++;
        }
        if(lcnt > 1) {
            ans = add(ans, mult(sub[node], n));
            return;
        }
        else {
            for(auto c : adj[node]) {
                if(c == par || dp[c]) continue;
                ans = add(ans, mult(sub[node] - sub[c], n));
                dfswin(c, node);
            }
            return;
        }
    }
    else {
        ans = add(ans, n - win);
        for(auto c : adj[node]) {
            if(c == par) continue;
            dfswin(c, node);
        }
    }

}
void dfslose(int node, int par) {
    if(!dep[node]) {
        ans = add(ans, win);
        for(auto c : adj[node]) {
            if(c == par) continue;
            dfslose(c, node);
        }
    }
    else {
        int lcnt = 0;
        for(auto c : adj[node]) {
            if(c == par) continue;
            if(!dp[c]) lcnt++;
        }
        if(lcnt > 1) {
            return;
        }
        else {
            for(auto c : adj[node]) {
                if(c == par || dp[c]) continue;
                dfslose(c, node);
            }
        }
    }
}

void solve() {
    cin >> n >> d;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if(n == 2) {
        cout << fp(4, d) << "\n";
        return;
    }

    dfsdp(1, 0);
    dpp[1] = 1;
    dfsdpp(1, 0);
    // for(int i = 1; i <= n; i++) {
    //     cout << "i: " << i << " dpp: " << dpp[i] << "\n";
    // }
    for(int i = 1; i <= n; i++) {
        if(i != 1 && dpp[i] == 0) {
            dpp[i] = 1;
        }
        else {
            dpp[i] = 0;
        }
        for(auto c : adj[i]) {
            if(!dp[c]) dpp[i] = 1;
        }
        win += !dpp[i];
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << " dp:" << dp[i] << " dpp:" << dpp[i] << "\n";
    // }
    if(dpp[1]) {
        dfswin(1, 0);
    }
    else {
        dfslose(1, 0);
    }
    cout << ans << "\n";
}

signed main() {
    fastio();
    solve();
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Incorrect 2 ms 3676 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 3424 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3640 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3672 KB Output is correct
8 Correct 2 ms 3672 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3676 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 35 ms 12112 KB Output is correct
13 Correct 63 ms 17460 KB Output is correct
14 Correct 27 ms 7884 KB Output is correct
15 Correct 39 ms 8280 KB Output is correct
16 Correct 34 ms 8272 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3640 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3672 KB Output is correct
8 Correct 2 ms 3672 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3676 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Incorrect 2 ms 3676 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 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3640 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3672 KB Output is correct
8 Correct 2 ms 3672 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3676 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 35 ms 12112 KB Output is correct
13 Correct 63 ms 17460 KB Output is correct
14 Correct 27 ms 7884 KB Output is correct
15 Correct 39 ms 8280 KB Output is correct
16 Correct 34 ms 8272 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Incorrect 2 ms 3676 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 3420 KB Output is correct
2 Incorrect 2 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -