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

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	Rubikun
提出日時	2024-07-27 00:13:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	46 ms / 2,000 ms
コード長	2,051 bytes
コンパイル時間	2,766 ms
コンパイル使用メモリ	209,964 KB
実行使用メモリ	13,920 KB
最終ジャッジ日時	2024-07-27 00:13:24
合計ジャッジ時間	7,667 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 10,416 KB
testcase_01	AC	5 ms 10,568 KB
testcase_02	AC	43 ms 13,768 KB
testcase_03	AC	42 ms 13,920 KB
testcase_04	AC	43 ms 13,892 KB
testcase_05	AC	46 ms 13,820 KB
testcase_06	AC	45 ms 13,896 KB
testcase_07	AC	42 ms 13,852 KB
testcase_08	AC	26 ms 11,336 KB
testcase_09	AC	39 ms 13,620 KB
testcase_10	AC	32 ms 12,588 KB
testcase_11	AC	24 ms 12,312 KB
testcase_12	AC	26 ms 11,576 KB
testcase_13	AC	21 ms 11,072 KB
testcase_14	AC	28 ms 12,040 KB
testcase_15	AC	30 ms 12,228 KB
testcase_16	AC	5 ms 10,452 KB
testcase_17	AC	6 ms 10,480 KB
testcase_18	AC	8 ms 10,952 KB
testcase_19	AC	6 ms 10,712 KB
testcase_20	AC	6 ms 10,452 KB
testcase_21	AC	6 ms 10,848 KB
testcase_22	AC	8 ms 10,760 KB
testcase_23	AC	7 ms 10,696 KB
testcase_24	AC	7 ms 10,704 KB
testcase_25	AC	5 ms 10,564 KB
testcase_26	AC	7 ms 10,836 KB
testcase_27	AC	4 ms 10,428 KB
testcase_28	AC	6 ms 10,716 KB
testcase_29	AC	8 ms 10,860 KB
testcase_30	AC	6 ms 10,432 KB
testcase_31	AC	5 ms 10,692 KB
testcase_32	AC	7 ms 10,660 KB
testcase_33	AC	8 ms 10,716 KB
testcase_34	AC	8 ms 10,732 KB
testcase_35	AC	7 ms 10,748 KB
testcase_36	AC	7 ms 10,692 KB
testcase_37	AC	8 ms 10,728 KB
testcase_38	AC	8 ms 10,588 KB
testcase_39	AC	7 ms 10,712 KB
testcase_40	AC	9 ms 10,800 KB
testcase_41	AC	8 ms 10,888 KB
testcase_42	AC	7 ms 10,972 KB
testcase_43	AC	8 ms 10,784 KB
testcase_44	AC	8 ms 11,076 KB
testcase_45	AC	7 ms 10,816 KB
testcase_46	AC	7 ms 10,784 KB
testcase_47	AC	8 ms 11,080 KB
testcase_48	AC	4 ms 10,536 KB
testcase_49	AC	4 ms 10,272 KB
testcase_50	AC	4 ms 10,500 KB
testcase_51	AC	4 ms 10,476 KB
testcase_52	AC	4 ms 10,480 KB
testcase_53	AC	4 ms 10,692 KB
testcase_54	AC	5 ms 10,820 KB
testcase_55	AC	5 ms 10,392 KB
testcase_56	AC	4 ms 10,568 KB
testcase_57	AC	5 ms 10,400 KB
testcase_58	AC	4 ms 10,376 KB
testcase_59	AC	6 ms 10,300 KB
testcase_60	AC	5 ms 11,076 KB
testcase_61	AC	5 ms 10,260 KB
testcase_62	AC	5 ms 10,620 KB
testcase_63	AC	5 ms 10,560 KB
testcase_64	AC	5 ms 10,472 KB
testcase_65	AC	5 ms 10,484 KB
testcase_66	AC	4 ms 10,484 KB
testcase_67	AC	5 ms 10,412 KB
testcase_68	AC	6 ms 10,404 KB
testcase_69	AC	4 ms 10,948 KB
testcase_70	AC	4 ms 10,460 KB
testcase_71	AC	5 ms 10,484 KB
testcase_72	AC	5 ms 10,428 KB
testcase_73	AC	5 ms 10,448 KB
testcase_74	AC	5 ms 10,428 KB
testcase_75	AC	5 ms 10,428 KB
testcase_76	AC	5 ms 10,436 KB
testcase_77	AC	5 ms 10,516 KB
testcase_78	AC	5 ms 10,692 KB
testcase_79	AC	6 ms 10,320 KB
testcase_80	AC	5 ms 10,400 KB
testcase_81	AC	6 ms 10,376 KB
testcase_82	AC	5 ms 10,340 KB
testcase_83	AC	5 ms 10,344 KB
testcase_84	AC	5 ms 10,392 KB
testcase_85	AC	5 ms 10,436 KB
testcase_86	AC	4 ms 10,344 KB
testcase_87	AC	5 ms 10,400 KB
testcase_88	AC	4 ms 10,436 KB
testcase_89	AC	4 ms 10,824 KB
testcase_90	AC	4 ms 10,540 KB
testcase_91	AC	4 ms 10,528 KB
testcase_92	AC	5 ms 10,412 KB
testcase_93	AC	4 ms 10,820 KB
testcase_94	AC	5 ms 10,412 KB
testcase_95	AC	5 ms 10,412 KB
testcase_96	AC	4 ms 10,436 KB
testcase_97	AC	3 ms 10,448 KB
testcase_98	AC	4 ms 10,436 KB
testcase_99	AC	4 ms 10,476 KB
testcase_100	AC	5 ms 10,356 KB
testcase_101	AC	5 ms 10,476 KB
testcase_102	AC	5 ms 10,412 KB
testcase_103	AC	4 ms 10,492 KB
testcase_104	AC	4 ms 10,432 KB
testcase_105	AC	4 ms 10,380 KB
testcase_106	AC	5 ms 10,428 KB
testcase_107	AC	5 ms 10,356 KB
testcase_108	AC	4 ms 10,484 KB
testcase_109	AC	5 ms 10,432 KB
testcase_110	AC	5 ms 10,284 KB
testcase_111	AC	5 ms 10,388 KB
testcase_112	AC	4 ms 10,472 KB
testcase_113	AC	5 ms 10,500 KB
testcase_114	AC	5 ms 10,264 KB
testcase_115	AC	4 ms 10,388 KB
testcase_116	AC	5 ms 10,668 KB
testcase_117	AC	4 ms 10,272 KB
testcase_118	AC	4 ms 10,320 KB
testcase_119	AC	4 ms 10,388 KB
testcase_120	AC	5 ms 10,576 KB
testcase_121	AC	4 ms 10,508 KB
testcase_122	AC	5 ms 10,448 KB
testcase_123	AC	4 ms 10,364 KB
testcase_124	AC	5 ms 10,436 KB
testcase_125	AC	4 ms 10,360 KB
testcase_126	AC	4 ms 10,404 KB
testcase_127	AC	4 ms 10,452 KB
testcase_128	AC	4 ms 10,408 KB
testcase_129	AC	6 ms 10,372 KB
testcase_130	AC	5 ms 10,384 KB
testcase_131	AC	3 ms 10,356 KB
testcase_132	AC	4 ms 10,248 KB
testcase_133	AC	4 ms 10,380 KB
testcase_134	AC	5 ms 10,820 KB
testcase_135	AC	5 ms 10,396 KB
testcase_136	AC	6 ms 10,436 KB
testcase_137	AC	5 ms 10,368 KB
testcase_138	AC	4 ms 10,388 KB
testcase_139	AC	4 ms 10,492 KB
testcase_140	AC	4 ms 10,292 KB
testcase_141	AC	4 ms 10,408 KB
testcase_142	AC	5 ms 10,248 KB
testcase_143	AC	6 ms 10,260 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

vector<int> G[MAX];
bool ne[MAX];
bool kai[MAX];

void mk(int u){
    for(int to:G[u]){
        mk(to);
        kai[u]^=kai[to];
    }
    ne[u]^=kai[u];
    if(ne[u]){
        kai[u]^=1;
    }
}

struct UF{
    int n;
    vector<int> par,size,edge;
    
    void init(int n_){
        n=n_;
        par.assign(n,-1);
        size.assign(n,1);
        edge.assign(n,0);
        
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    
    int root(int a){
        if(par[a]==a) return a;
        else return par[a]=root(par[a]);
    }
    
    void unite(int a,int b){
        edge[root(a)]++;
        if(root(a)!=root(b)){
            size[root(a)]+=size[root(b)];
            edge[root(a)]+=edge[root(b)];
            par[root(b)]=root(a);
        }
    }
    
    bool check(int a,int b){
        return root(a)==root(b);
    }
};

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    for(int i=1;i<N;i++){
        int p;cin>>p;p--;
        G[p].push_back(i);
    }
    string S;cin>>S;
    for(int i=0;i<si(S);i++){
        if(S[i]=='#') ne[i+1]=1;
    }
    mk(0);
    
    UF uf;uf.init(N);
    for(int i=0;i<N;i++){
        if(ne[i]) uf.size[i]=1;
        else uf.size[i]=0;
    }
    
    int K;cin>>K;
    for(int i=0;i<K;i++){
        int a,b;cin>>a>>b;a--;b--;
        uf.unite(a,b);
    }
    
    for(int i=0;i<N;i++){
        if(uf.root(i)==i){
            if(uf.size[i]%2){
                cout<<"No\n";
                return 0;
            }
        }
    }
    
    cout<<"Yes\n";
}

yukicoder

結果

テストケース

ソースコード