結果

問題 No.2726 Rooted Tree Nim
ユーザー 🦠みどりむし🦠みどりむし
提出日時 2024-04-12 21:30:50
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 302 ms / 2,000 ms
コード長 3,164 bytes
コンパイル時間 2,664 ms
コンパイル使用メモリ 252,984 KB
実行使用メモリ 20,480 KB
最終ジャッジ日時 2024-10-02 23:01:11
合計ジャッジ時間 6,499 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 302 ms
5,248 KB
testcase_02 AC 202 ms
7,424 KB
testcase_03 AC 252 ms
20,480 KB
testcase_04 AC 258 ms
20,480 KB
testcase_05 AC 186 ms
15,776 KB
testcase_06 AC 178 ms
15,772 KB
testcase_07 AC 219 ms
16,128 KB
testcase_08 AC 223 ms
16,128 KB
testcase_09 AC 186 ms
6,528 KB
testcase_10 AC 190 ms
6,324 KB
testcase_11 AC 193 ms
7,680 KB
testcase_12 AC 216 ms
14,592 KB
testcase_13 AC 187 ms
6,400 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ 20 GCC */

#include <bits/stdc++.h>

/* [begin]: snippet/aliases.hpp */
#include <cstdint>
#include <utility>
#include <vector>
#include <ranges>
/* [begin]: internal/dev_env.hpp */
#ifdef LOCAL_JUDGE
inline constexpr bool DEV_ENV = true; inline constexpr bool NO_EXCEPT = false;
#else
inline constexpr bool DEV_ENV = false; inline constexpr bool NO_EXCEPT = true;
#endif
#if __cplusplus >= 202100L
#define CPP20 true
#define CPP23 true
#elif __cplusplus >= 202002L
#define CPP20 true
#define CPP23 false
#else
#define CPP20 false
#define CPP23 false
#endif
/* [end]: internal/dev_env.hpp*/
/* [begin]: snippet/internal/types.hpp */
namespace lib { using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t; using u128 = __uint128_t;
#endif
using uint = unsigned; using ll = long long; using ull = unsigned long long; using ld = long double; }
/* [end]: snippet/internal/types.hpp*/
#define until(...) while(!(__VA_ARGS__))
#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }
#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))
#define $F first
#define $S second
namespace lib { constexpr char LN = '\n'; constexpr char SPC = ' '; constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; constexpr std::pair<int,int> DIRS4P[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { 0, 0 } }; constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; constexpr std::pair<int,int> DIRS8P[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { 0, 0 } }; template<class T> using spair = std::pair<T,T>; } namespace std { using bit_reference = std::vector<bool>::reference; bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; } bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; } }
/* [end]: snippet/aliases.hpp*/

void solve();

signed main() {
    int $ = 1;
    std::cin >> $;
    for(int _ = 0; _ < $; ++_) {
        solve();
    }
    return 0;
}

void solve() {
    int n, k; std::cin >> n >> k;
    std::vector<std::vector<int>> tree(n);

    for(const int _ : std::views::iota(0, n - 1)) {
        int x, y; std::cin >> x >> y; --x, --y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }

    std::vector<unsigned> a(n); for(auto& v : a) std::cin >> v;

    unsigned sum = 0;

    auto dfs = [&](auto&& dfs, int v, int p, int d) -> void {
        if(d % 2) sum ^= a[v] % (k + 1);
        for(const auto& nv : tree[v]) {
            if(nv == p) continue;
            dfs(dfs, nv, v, d + 1);
        }
    };
    dfs(dfs, 0, -1, 0);

    std::cout << (sum == 0 ? "P" : "K") << "\n";
}
0