oj.uz

Submission #701632

# Submission time Handle Problem Language Result Execution time Memory
701632 2023-02-21T15:51:45 Z Cyanmond Star Trek (CEOI20_startrek) C++17
7 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -