#998197 (C++17) No.2822 Lights Up! (Tree Edition)

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	GOTKAKO
提出日時	2024-07-27 16:24:06
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	65 ms / 2,000 ms
コード長	1,691 bytes
コンパイル時間	2,693 ms
コンパイル使用メモリ	215,256 KB
実行使用メモリ	11,264 KB
最終ジャッジ日時	2024-07-27 16:24:15
合計ジャッジ時間	7,700 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	59 ms 11,264 KB
testcase_03	AC	58 ms 11,008 KB
testcase_04	AC	57 ms 10,880 KB
testcase_05	AC	65 ms 11,008 KB
testcase_06	AC	56 ms 10,624 KB
testcase_07	AC	57 ms 10,752 KB
testcase_08	AC	29 ms 6,272 KB
testcase_09	AC	53 ms 10,368 KB
testcase_10	AC	42 ms 8,448 KB
testcase_11	AC	33 ms 7,424 KB
testcase_12	AC	33 ms 6,656 KB
testcase_13	AC	26 ms 5,504 KB
testcase_14	AC	38 ms 7,040 KB
testcase_15	AC	36 ms 7,296 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	7 ms 5,376 KB
testcase_19	AC	4 ms 5,376 KB
testcase_20	AC	5 ms 5,376 KB
testcase_21	AC	6 ms 5,376 KB
testcase_22	AC	6 ms 5,376 KB
testcase_23	AC	6 ms 5,376 KB
testcase_24	AC	5 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	5 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	5 ms 5,376 KB
testcase_29	AC	7 ms 5,376 KB
testcase_30	AC	5 ms 5,376 KB
testcase_31	AC	4 ms 5,376 KB
testcase_32	AC	7 ms 5,376 KB
testcase_33	AC	7 ms 5,376 KB
testcase_34	AC	7 ms 5,376 KB
testcase_35	AC	7 ms 5,376 KB
testcase_36	AC	7 ms 5,376 KB
testcase_37	AC	7 ms 5,376 KB
testcase_38	AC	7 ms 5,376 KB
testcase_39	AC	7 ms 5,376 KB
testcase_40	AC	7 ms 5,376 KB
testcase_41	AC	7 ms 5,376 KB
testcase_42	AC	7 ms 5,376 KB
testcase_43	AC	7 ms 5,376 KB
testcase_44	AC	7 ms 5,376 KB
testcase_45	AC	8 ms 5,376 KB
testcase_46	AC	7 ms 5,376 KB
testcase_47	AC	7 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	2 ms 5,376 KB
testcase_54	AC	2 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	2 ms 5,376 KB
testcase_57	AC	3 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	3 ms 5,376 KB
testcase_62	AC	3 ms 5,376 KB
testcase_63	AC	3 ms 5,376 KB
testcase_64	AC	2 ms 5,376 KB
testcase_65	AC	3 ms 5,376 KB
testcase_66	AC	2 ms 5,376 KB
testcase_67	AC	3 ms 5,376 KB
testcase_68	AC	2 ms 5,376 KB
testcase_69	AC	3 ms 5,376 KB
testcase_70	AC	2 ms 5,376 KB
testcase_71	AC	2 ms 5,376 KB
testcase_72	AC	3 ms 5,376 KB
testcase_73	AC	2 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	2 ms 5,376 KB
testcase_79	AC	3 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	2 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	3 ms 5,376 KB
testcase_134	AC	3 ms 5,376 KB
testcase_135	AC	2 ms 5,376 KB
testcase_136	AC	2 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>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> P(N-1);
    for(auto &p : P) cin >> p,p--;
    string s; cin >> s;
    s.insert(s.begin(),'.');
    vector<vector<int>> Graph(N);
    for(int i=0; i<N-1; i++){
        Graph.at(P.at(i)).push_back(i+1);
        Graph.at(i+1).push_back(P.at(i));
    }
    vector<int> diff(N);
    auto dfs = [&](auto dfs,int pos,int back) -> void {
        bool leaf = true;
        int black = 0;
        for(auto to : Graph.at(pos)){
            if(to == back) continue;
            leaf = false;
            dfs(dfs,to,pos);
            if(s.at(to) == '#') black ^= 1;  
        }
        if(leaf && s.at(pos) == '#') diff.at(pos) = 1;
        if(!leaf){
            if(s.at(pos) == '#') diff.at(pos) = black^1;
            else diff.at(pos) = black; 
        }
    };
    dfs(dfs,0,-1);
    for(auto &d : diff) d &= 1;

    Graph.assign(N,{});
    int K; cin >> K;
    while(K--){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    vector<bool> already(N);
    bool yes = true;
    for(int i=0; i<N; i++) if(already.at(i) == false){
        already.at(i) = true;
        queue<int> Q; Q.push(i);
        int sumd = 0;
        while(Q.size()){
            int pos = Q.front(); Q.pop();
            sumd += diff.at(pos);
            for(auto to : Graph.at(pos)) if(already.at(to) == false){
                already.at(to) = true; Q.push(to); 
            }
        }
        if(sumd%2) yes = false;
    }
    if(yes) cout << "Yes" << endl;
    else cout << "No" << endl;
}

yukicoder

結果

テストケース

ソースコード