Submission #701632

#	Time	Username	Problem	Language	Result	Execution time	Memory
701632		Cyanmond	Star Trek (CEOI20_startrek)	C++17	7 / 100	1 ms	340 KiB

startrek

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 mod = 1000000007;
i64 add(i64 a, i64 b) {
    return (a + b) % mod;
}
i64 sub(i64 a, i64 b) {
    return (a + mod - b) % mod;
}
i64 mul(i64 a, i64 b) {
    return (a * b) % mod;
}
void eadd(i64 &a, i64 b) {
    a = add(a, b);
}
void esub(i64 &a, i64 b) {
    a = sub(a, b);
}
void emul(i64 &a, i64 b) {
    a = mul(a, b);
}

i64 pow(i64 a, i64 n) {
    i64 ret = 1;
    while (n != 0) {
        if (n % 2 == 1) {
            emul(ret, a);
        }
        emul(a, a);
        n /= 2;
    }
    return ret;
}

int main() {
    int N;
    i64 D;
    std::cin >> N >> D;
    if (N == 2) {
        std::cout << pow(4, D) << std::endl;
        return 0;
    }
    std::vector<int> A(N - 1), B(N - 1);
    std::vector<std::vector<int>> tree(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        tree[A[i]].push_back(B[i]);
        tree[B[i]].push_back(A[i]);
    }

    // first game
    // rerooting
    std::vector<bool> dpParent(N);
    auto dfs1 = [&](auto &&self, const int v, const int p) -> void {
        for (int i = 0; i < (int)tree[v].size(); ++i) {
            const int t = tree[v][i];
            if (t == p) {
                std::swap(tree[v][i], tree[v][0]);
            } else {
                self(self, t, v);
            }
        }
    };
    dfs1(dfs1, 0, -1);
    auto dfs2 = [&](auto &&self, const int v, const int p) -> bool {
        if (v != 0 and tree[v].size() == 1) {
            return dpParent[v] = false;
        }
        bool ret = false;
        for (int i = 0; i < (int)tree[v].size(); ++i) {
            const int t = tree[v][i];
            if (t == p) {
                continue;
            }
            ret |= not self(self, t, v);
        }
        return dpParent[v] = ret;
    };
    dfs2(dfs2, 0, -1);

    std::vector<std::vector<bool>> dpChildren;
    auto dfs3 = [&](auto &&self, const int v, const int p, bool dpvPar) -> bool {

    };
}

Compilation message (stderr)

startrek.cpp: In lambda function:
startrek.cpp:86:5: warning: no return statement in function returning non-void [-Wreturn-type]
   86 |     };
      |     ^
startrek.cpp: In function 'int main()':
startrek.cpp:84:10: warning: variable 'dfs3' set but not used [-Wunused-but-set-variable]
   84 |     auto dfs3 = [&](auto &&self, const int v, const int p, bool dpvPar) -> bool {
      |          ^~~~

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