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

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	Astral__
提出日時	2024-07-26 23:54:48
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,021 bytes
コンパイル時間	9,961 ms
コンパイル使用メモリ	556,784 KB
実行使用メモリ	25,124 KB
最終ジャッジ日時	2024-07-26 23:55:11
合計ジャッジ時間	22,272 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	3 ms 6,812 KB
testcase_02	AC	809 ms 25,124 KB
testcase_03	WA	-
testcase_04	AC	330 ms 25,000 KB
testcase_05	AC	935 ms 25,000 KB
testcase_06	AC	177 ms 25,052 KB
testcase_07	AC	238 ms 24,952 KB
testcase_08	AC	280 ms 16,048 KB
testcase_09	AC	352 ms 23,240 KB
testcase_10	WA	-
testcase_11	AC	115 ms 14,976 KB
testcase_12	AC	194 ms 17,280 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	5 ms 6,940 KB
testcase_17	AC	9 ms 6,940 KB
testcase_18	AC	23 ms 6,940 KB
testcase_19	AC	5 ms 6,940 KB
testcase_20	AC	14 ms 6,940 KB
testcase_21	WA	-
testcase_22	AC	8 ms 6,940 KB
testcase_23	AC	31 ms 6,940 KB
testcase_24	AC	6 ms 6,944 KB
testcase_25	AC	3 ms 6,944 KB
testcase_26	AC	22 ms 6,944 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	12 ms 6,940 KB
testcase_32	AC	21 ms 6,940 KB
testcase_33	AC	28 ms 6,944 KB
testcase_34	WA	-
testcase_35	AC	25 ms 6,940 KB
testcase_36	WA	-
testcase_37	AC	16 ms 6,940 KB
testcase_38	AC	13 ms 6,940 KB
testcase_39	AC	11 ms 6,940 KB
testcase_40	WA	-
testcase_41	AC	18 ms 6,940 KB
testcase_42	AC	11 ms 6,940 KB
testcase_43	AC	39 ms 6,944 KB
testcase_44	AC	18 ms 6,944 KB
testcase_45	AC	53 ms 6,944 KB
testcase_46	AC	28 ms 6,940 KB
testcase_47	WA	-
testcase_48	AC	3 ms 6,940 KB
testcase_49	WA	-
testcase_50	WA	-
testcase_51	AC	3 ms 6,944 KB
testcase_52	AC	5 ms 6,940 KB
testcase_53	AC	3 ms 6,940 KB
testcase_54	AC	4 ms 6,944 KB
testcase_55	WA	-
testcase_56	AC	3 ms 6,944 KB
testcase_57	AC	3 ms 6,940 KB
testcase_58	AC	3 ms 6,944 KB
testcase_59	AC	3 ms 6,940 KB
testcase_60	AC	4 ms 6,944 KB
testcase_61	WA	-
testcase_62	WA	-
testcase_63	AC	3 ms 6,940 KB
testcase_64	AC	3 ms 6,940 KB
testcase_65	AC	3 ms 6,944 KB
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	AC	3 ms 6,940 KB
testcase_70	WA	-
testcase_71	AC	3 ms 6,940 KB
testcase_72	AC	3 ms 6,944 KB
testcase_73	AC	3 ms 6,940 KB
testcase_74	AC	5 ms 6,940 KB
testcase_75	AC	3 ms 6,944 KB
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	AC	2 ms 6,940 KB
testcase_80	AC	2 ms 6,940 KB
testcase_81	WA	-
testcase_82	AC	2 ms 6,948 KB
testcase_83	AC	2 ms 6,944 KB
testcase_84	AC	2 ms 6,944 KB
testcase_85	AC	2 ms 6,940 KB
testcase_86	AC	2 ms 6,944 KB
testcase_87	WA	-
testcase_88	AC	2 ms 6,940 KB
testcase_89	AC	2 ms 6,940 KB
testcase_90	AC	2 ms 6,944 KB
testcase_91	WA	-
testcase_92	AC	2 ms 6,944 KB
testcase_93	WA	-
testcase_94	WA	-
testcase_95	AC	2 ms 6,940 KB
testcase_96	AC	2 ms 6,940 KB
testcase_97	AC	2 ms 6,944 KB
testcase_98	WA	-
testcase_99	AC	1 ms 6,940 KB
testcase_100	WA	-
testcase_101	AC	1 ms 6,940 KB
testcase_102	WA	-
testcase_103	AC	2 ms 6,944 KB
testcase_104	AC	2 ms 6,940 KB
testcase_105	WA	-
testcase_106	WA	-
testcase_107	AC	2 ms 6,944 KB
testcase_108	AC	2 ms 6,944 KB
testcase_109	WA	-
testcase_110	WA	-
testcase_111	WA	-
testcase_112	AC	2 ms 6,944 KB
testcase_113	AC	4 ms 6,940 KB
testcase_114	WA	-
testcase_115	WA	-
testcase_116	AC	2 ms 6,944 KB
testcase_117	AC	4 ms 6,940 KB
testcase_118	WA	-
testcase_119	AC	2 ms 6,940 KB
testcase_120	WA	-
testcase_121	WA	-
testcase_122	WA	-
testcase_123	AC	4 ms 6,944 KB
testcase_124	WA	-
testcase_125	WA	-
testcase_126	AC	2 ms 6,944 KB
testcase_127	WA	-
testcase_128	AC	4 ms 6,940 KB
testcase_129	WA	-
testcase_130	WA	-
testcase_131	WA	-
testcase_132	AC	3 ms 6,940 KB
testcase_133	AC	4 ms 6,940 KB
testcase_134	AC	3 ms 6,944 KB
testcase_135	WA	-
testcase_136	AC	3 ms 6,940 KB
testcase_137	WA	-
testcase_138	AC	4 ms 6,940 KB
testcase_139	AC	4 ms 6,944 KB
testcase_140	AC	3 ms 6,940 KB
testcase_141	AC	3 ms 6,940 KB
testcase_142	AC	3 ms 6,940 KB
testcase_143	WA	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>

// 任意長整数型
using Bint = boost::multiprecision::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using Real =
    boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;
using Rat = boost::rational<Bint>;

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
TT using vvec = vec<vec<T>>;
TT using vvvec = vec<vvec<T>>;
TT using minheap = priority_queue<T, vector<T>, greater<T>>;
TT using maxheap = priority_queue<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
TT auto prev_itr(vec<T> &A, T x) {  // must sorted
    auto res = lower_bound(all(A), x);
    if (res == A.begin())
        return A.end();
    else
        return --res;
}
TT auto next_itr(vec<T> &A, T x) {  // must sorted
    return upper_bound(all(A), x) - A.begin();
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

int main() {
    ll n;
    cin >> n;
    vec<vec<int>> g(n);
    rep(i, 1, n) {
        int p;
        cin >> p;
        p--;
        g[i].push_back(p);
        g[p].push_back(i);
    }

    vec<int> col(n, 0);
    rep(i, 1, n) {
        char c;
        cin >> c;
        if (c == '#') col[i] = 1; //変える必要がある。
    }

    ll k;
    cin >> k;
    vec<int> U(k), V(k);
    rep(i, 0, k) {
        cin >> U[i] >> V[i];
        U[i]--, V[i]--;
    }
    vec<set<int>> rev(n);
    rep(i, 0, k) {
        rev[U[i]].insert(i);
        rev[V[i]].insert(i);
    }


    vec<int> base(n, -1);

    auto path_xor = [&](int v, int id1, int id2) {  // id2を変更する。
     
        int nl, nr;
        if (U[id1] == v)
            nl = V[id1];
        else
            nl = U[id1];

        if (U[id2] == v)
            nr = V[id2];
        else
            nr = U[id2];

        rev[U[id2]].erase(id2);
        rev[V[id2]].erase(id2);
        U[id2] = nl;
        V[id2] = nr;
        if (nl == nr) return;

        rev[U[id2]].insert(id2);
        rev[V[id2]].insert(id2);
        return;
    };

    set<int> base_used;

    auto dfs = [&](auto f, int v, int p = -1) -> void {
        for(int to : g[v]) if(to != p) {
            f(f, to, v);
        }

        int use = -1;
        for(int id : rev[v]) if(base_used.count(id) == 0) use = id;
        if(use == -1) return;

        base_used.insert(use);
        vec<int> tar;
        for(int id : rev[v]) if(id != use) tar.push_back(id);
        sort(all(tar));
        tar.erase(unique(all(tar)), tar.end());
        for(int id : tar) path_xor(v, use, id);
        /*
        vec<int> era;
        for(int di : rev[v]) era.push_back(di);

        for(int di : era) path_xor(v, use, di);
        */

        base[v] = use;
        return;
    };

    dfs(dfs, 0);

    vec<int> imos(n, 0);

    set<int> already;

    rep(i, 0, n) if(base[i] != -1 && col[i] == 1 && !already.count(base[i])) {
        int id = base[i];
        already.insert(id);

        imos[U[id]]++;
        imos[V[id]]++;
    }

    auto dfs2 = [&](auto f, int v, int p = -1) -> bool {
        for(int to : g[v]) if(to != p) {
            if(f(f, to, v) == false) {
                return false;
            }
        }

        if(p != -1) imos[p] += imos[v];

        if((imos[v] % 2) != col[v]) {
            return false;
        }
        else return true;
    };


    if(dfs2(dfs2, 0)) cout <<  "Yes" << endl;
    else cout << "No" << endl;


}

yukicoder

結果

テストケース

ソースコード