#997906 (C++23) No.2822 Lights Up! (Tree Edition)

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	rniya
提出日時	2024-07-26 23:15:43
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	51 ms / 2,000 ms
コード長	2,027 bytes
コンパイル時間	3,288 ms
コンパイル使用メモリ	255,232 KB
実行使用メモリ	8,960 KB
最終ジャッジ日時	2024-07-26 23:15:51
合計ジャッジ時間	8,228 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	44 ms 8,960 KB
testcase_03	AC	45 ms 8,960 KB
testcase_04	AC	45 ms 8,960 KB
testcase_05	AC	45 ms 8,960 KB
testcase_06	AC	51 ms 8,960 KB
testcase_07	AC	45 ms 8,960 KB
testcase_08	AC	25 ms 5,376 KB
testcase_09	AC	41 ms 8,448 KB
testcase_10	AC	33 ms 6,940 KB
testcase_11	AC	24 ms 6,528 KB
testcase_12	AC	27 ms 5,504 KB
testcase_13	AC	19 ms 5,376 KB
testcase_14	AC	25 ms 6,272 KB
testcase_15	AC	29 ms 6,016 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	5 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	4 ms 5,376 KB
testcase_21	AC	4 ms 5,376 KB
testcase_22	AC	4 ms 5,376 KB
testcase_23	AC	5 ms 5,376 KB
testcase_24	AC	4 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	4 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	4 ms 5,376 KB
testcase_29	AC	6 ms 5,376 KB
testcase_30	AC	4 ms 5,376 KB
testcase_31	AC	3 ms 5,376 KB
testcase_32	AC	6 ms 5,376 KB
testcase_33	AC	5 ms 5,376 KB
testcase_34	AC	6 ms 5,376 KB
testcase_35	AC	5 ms 5,376 KB
testcase_36	AC	6 ms 5,376 KB
testcase_37	AC	6 ms 5,376 KB
testcase_38	AC	6 ms 5,376 KB
testcase_39	AC	5 ms 5,376 KB
testcase_40	AC	6 ms 5,376 KB
testcase_41	AC	5 ms 5,376 KB
testcase_42	AC	5 ms 5,376 KB
testcase_43	AC	6 ms 5,376 KB
testcase_44	AC	6 ms 5,376 KB
testcase_45	AC	5 ms 5,376 KB
testcase_46	AC	6 ms 5,376 KB
testcase_47	AC	6 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB
testcase_50	AC	2 ms 5,376 KB
testcase_51	AC	2 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	3 ms 5,376 KB
testcase_54	AC	2 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	3 ms 5,376 KB
testcase_57	AC	2 ms 5,376 KB
testcase_58	AC	2 ms 5,376 KB
testcase_59	AC	2 ms 5,376 KB
testcase_60	AC	2 ms 5,376 KB
testcase_61	AC	2 ms 5,376 KB
testcase_62	AC	2 ms 5,376 KB
testcase_63	AC	2 ms 5,376 KB
testcase_64	AC	2 ms 5,376 KB
testcase_65	AC	2 ms 5,376 KB
testcase_66	AC	2 ms 5,376 KB
testcase_67	AC	2 ms 5,376 KB
testcase_68	AC	3 ms 5,376 KB
testcase_69	AC	2 ms 5,376 KB
testcase_70	AC	3 ms 5,376 KB
testcase_71	AC	3 ms 5,376 KB
testcase_72	AC	2 ms 5,376 KB
testcase_73	AC	3 ms 5,376 KB
testcase_74	AC	2 ms 5,376 KB
testcase_75	AC	2 ms 5,376 KB
testcase_76	AC	2 ms 5,376 KB
testcase_77	AC	2 ms 5,376 KB
testcase_78	AC	3 ms 5,376 KB
testcase_79	AC	2 ms 5,376 KB
testcase_80	AC	2 ms 5,376 KB
testcase_81	AC	2 ms 5,376 KB
testcase_82	AC	2 ms 5,376 KB
testcase_83	AC	2 ms 5,376 KB
testcase_84	AC	2 ms 5,376 KB
testcase_85	AC	2 ms 5,376 KB
testcase_86	AC	2 ms 5,376 KB
testcase_87	AC	2 ms 5,376 KB
testcase_88	AC	2 ms 5,376 KB
testcase_89	AC	2 ms 5,376 KB
testcase_90	AC	2 ms 5,376 KB
testcase_91	AC	2 ms 5,376 KB
testcase_92	AC	2 ms 5,376 KB
testcase_93	AC	2 ms 5,376 KB
testcase_94	AC	2 ms 5,376 KB
testcase_95	AC	2 ms 5,376 KB
testcase_96	AC	2 ms 5,376 KB
testcase_97	AC	2 ms 5,376 KB
testcase_98	AC	2 ms 5,376 KB
testcase_99	AC	2 ms 5,376 KB
testcase_100	AC	2 ms 5,376 KB
testcase_101	AC	2 ms 5,376 KB
testcase_102	AC	2 ms 5,376 KB
testcase_103	AC	2 ms 5,376 KB
testcase_104	AC	2 ms 5,376 KB
testcase_105	AC	2 ms 5,376 KB
testcase_106	AC	2 ms 5,376 KB
testcase_107	AC	2 ms 5,376 KB
testcase_108	AC	2 ms 5,376 KB
testcase_109	AC	2 ms 5,376 KB
testcase_110	AC	2 ms 5,376 KB
testcase_111	AC	2 ms 5,376 KB
testcase_112	AC	2 ms 5,376 KB
testcase_113	AC	2 ms 5,376 KB
testcase_114	AC	2 ms 5,376 KB
testcase_115	AC	2 ms 5,376 KB
testcase_116	AC	2 ms 5,376 KB
testcase_117	AC	2 ms 5,376 KB
testcase_118	AC	2 ms 5,376 KB
testcase_119	AC	2 ms 5,376 KB
testcase_120	AC	2 ms 5,376 KB
testcase_121	AC	2 ms 5,376 KB
testcase_122	AC	2 ms 5,376 KB
testcase_123	AC	2 ms 5,376 KB
testcase_124	AC	2 ms 5,376 KB
testcase_125	AC	3 ms 5,376 KB
testcase_126	AC	2 ms 5,376 KB
testcase_127	AC	2 ms 5,376 KB
testcase_128	AC	2 ms 5,376 KB
testcase_129	AC	2 ms 5,376 KB
testcase_130	AC	2 ms 5,376 KB
testcase_131	AC	2 ms 5,376 KB
testcase_132	AC	2 ms 5,376 KB
testcase_133	AC	2 ms 5,376 KB
testcase_134	AC	2 ms 5,376 KB
testcase_135	AC	2 ms 5,376 KB
testcase_136	AC	3 ms 5,376 KB
testcase_137	AC	2 ms 5,376 KB
testcase_138	AC	2 ms 5,376 KB
testcase_139	AC	2 ms 5,376 KB
testcase_140	AC	2 ms 5,376 KB
testcase_141	AC	2 ms 5,376 KB
testcase_142	AC	2 ms 5,376 KB
testcase_143	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

#include <atcoder/dsu>

using ll = long long;

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    for (int i = 1; i < N; i++) {
        int P;
        cin >> P;
        G[--P].emplace_back(i);
    }
    string s;
    cin >> s;
    vector<int> S(N);
    for (int i = 1; i < N; i++) S[i] = (s[i - 1] == '#');
    S[0] = 0;
    auto dfs = [&](auto self, int v) -> void {
        for (int& u : G[v]) {
            S[v] ^= S[u];
            self(self, u);
        }
    };
    dfs(dfs, 0);
    debug(S);

    atcoder::dsu dsu(N);
    int K;
    cin >> K;
    for (; K--;) {
        int U, V;
        cin >> U >> V;
        dsu.merge(--U, --V);
    }
    vector<int> sum(N, 0);
    for (int i = 0; i < N; i++) sum[dsu.leader(i)] ^= S[i];
    for (int i = 0; i < N; i++) {
        if (sum[i] == 1) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    return 0;
}

yukicoder

結果

テストケース

ソースコード