Submission #336773

#	Time	Username	Problem	Language	Result	Execution time	Memory
336773		dolphingarlic	Star Trek (CEOI20_startrek)	C++14	23 / 100	84 ms	12160 KiB

startrek

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<int> graph[100001];
ll win_as_root[100001], critical[100001];

void dfs1(int node = 1, int parent = 0) {
    for (int i : graph[node]) if (i != parent) {
        dfs1(i, node);
        win_as_root[node] += (win_as_root[i] == 0);
    }
    if (!win_as_root[node]) critical[node] = 1;
    for (int i : graph[node]) if (i != parent) {
        if ((win_as_root[node] == 1 && !win_as_root[i]) || !win_as_root[node])
            critical[node] += critical[i];
    }
}

void dfs2(int node = 1, int parent = 0, int anc = 1) {
    win_as_root[node] += (anc == 0);
    for (int i : graph[node]) if (i != parent) {
        dfs2(i, node, win_as_root[node] - (win_as_root[i] == 0));
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, d;
    cin >> n >> d;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs1();
    dfs2();

    ll lose_cnt = 0;
    for (int i = 1; i <= n; i++) lose_cnt += (win_as_root[i] == 0);
    if (win_as_root[1])
        cout << n * n - lose_cnt * critical[1];
    else
        cout << lose_cnt * critical[1];
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15