提出 #69056458

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define in(n) long long int n; cin >> n;
#define out(i) cout << i << endl;
#define ordered_set tree< pair<lli, lli>, null_type, less<pair<lli, lli>>, rb_tree_tag, tree_order_statistics_node_update >
const int md = 1e9 + 7;

class joint{
    private:
    vector<int> par;
    vector<int> sizes;
    vector<int> blacks;
    vector<int> lol_black;
    public:
    joint(int size) :par(size), sizes(size,1), blacks(size, 0), lol_black(size, 0){
        for(int i = 0; i<size; i++){
            par[i] = i;
        }
    }
    int find(int x){
        return par[x] == x? x : (par[x] = find(par[x]));
    }
    bool unite(int x, int y){
        x = find(x); y =find(y);
        if(x == y){return false;}
        if(sizes[x]<sizes[y]){
            swap(x,y);
        }
        sizes[x]+=sizes[y];
        blacks[x]+=blacks[y];
        blacks[y] = 0;
        par[y] = x;
        return true;
    }
    bool connected(int x, int y){
        return find(x) == find(y);
    }
    bool find_black(int x){
        int ans = blacks[find(x)];
        if(ans>0){
            return true;
        }
        return false;
    }
    void remove_black(int x){
        x = find(x);
        blacks[x] = blacks[x]-1;
    }
    void topel(int x){
        int parx = find(x);
        if(lol_black[x]==1){
            lol_black[x] = 0;
            // blacks[x]
            blacks[parx] = blacks[parx]-1;
        }
        else{
            lol_black[x] = 1;
            blacks[parx] = blacks[parx]+1;
        }
    }
};

int main() {
    in(n) in(q);
    joint dsu(n+1);
    while(q--){
        in(qtype)
        if(qtype == 1){
            in(u) in(v)
            dsu.unite(u,v);
        }
        if(qtype == 2){
            in(x)
            dsu.topel(x);
        }
        if(qtype == 3){
            in(x)
            if(dsu.find_black(x)){
                cout<<"YES"<<endl;
            }
            else{
                cout<<"NO"<<endl;
            }
        }
    }

}

提出情報

提出日時
問題 E - Reachability Query
ユーザ c_vishal
言語 C++ 20 (gcc 12.2)
得点 0
コード長 2223 Byte
結果 WA
実行時間 720 ms
メモリ 6472 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 450
結果
WA × 1
AC × 1
WA × 84
セット名 テストケース
Sample sample_01.txt
All sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt, test_71.txt, test_72.txt, test_73.txt, test_74.txt, test_75.txt, test_76.txt, test_77.txt, test_78.txt, test_79.txt, test_80.txt, test_81.txt, test_82.txt, test_83.txt, test_84.txt
ケース名 結果 実行時間 メモリ
sample_01.txt WA 1 ms 3492 KiB
test_01.txt AC 1 ms 3600 KiB
test_02.txt WA 1 ms 3488 KiB
test_03.txt WA 670 ms 3536 KiB
test_04.txt WA 673 ms 3540 KiB
test_05.txt WA 112 ms 3676 KiB
test_06.txt WA 531 ms 3492 KiB
test_07.txt WA 341 ms 3504 KiB
test_08.txt WA 309 ms 3628 KiB
test_09.txt WA 142 ms 3500 KiB
test_10.txt WA 366 ms 3548 KiB
test_11.txt WA 299 ms 3460 KiB
test_12.txt WA 310 ms 3416 KiB
test_13.txt WA 181 ms 3544 KiB
test_14.txt WA 272 ms 3504 KiB
test_15.txt WA 325 ms 3548 KiB
test_16.txt WA 179 ms 3552 KiB
test_17.txt WA 168 ms 3464 KiB
test_18.txt WA 461 ms 3484 KiB
test_19.txt WA 349 ms 3548 KiB
test_20.txt WA 259 ms 3496 KiB
test_21.txt WA 233 ms 6324 KiB
test_22.txt WA 320 ms 6268 KiB
test_23.txt WA 501 ms 6332 KiB
test_24.txt WA 571 ms 6232 KiB
test_25.txt WA 481 ms 6328 KiB
test_26.txt WA 416 ms 6252 KiB
test_27.txt WA 464 ms 6248 KiB
test_28.txt WA 280 ms 6280 KiB
test_29.txt WA 529 ms 6284 KiB
test_30.txt WA 501 ms 6376 KiB
test_31.txt WA 476 ms 6228 KiB
test_32.txt WA 554 ms 6464 KiB
test_33.txt WA 455 ms 6400 KiB
test_34.txt WA 370 ms 6356 KiB
test_35.txt WA 533 ms 6236 KiB
test_36.txt WA 356 ms 6368 KiB
test_37.txt WA 454 ms 6232 KiB
test_38.txt WA 215 ms 6284 KiB
test_39.txt WA 414 ms 6340 KiB
test_40.txt WA 200 ms 6404 KiB
test_41.txt WA 324 ms 6464 KiB
test_42.txt WA 364 ms 6236 KiB
test_43.txt WA 436 ms 6464 KiB
test_44.txt WA 397 ms 6308 KiB
test_45.txt WA 428 ms 6400 KiB
test_46.txt WA 307 ms 6236 KiB
test_47.txt WA 261 ms 6316 KiB
test_48.txt WA 380 ms 6324 KiB
test_49.txt WA 296 ms 6280 KiB
test_50.txt WA 352 ms 6324 KiB
test_51.txt WA 209 ms 6468 KiB
test_52.txt WA 538 ms 6268 KiB
test_53.txt WA 422 ms 6248 KiB
test_54.txt WA 357 ms 6320 KiB
test_55.txt WA 535 ms 6284 KiB
test_56.txt WA 478 ms 6276 KiB
test_57.txt WA 279 ms 6248 KiB
test_58.txt WA 238 ms 6472 KiB
test_59.txt WA 582 ms 6328 KiB
test_60.txt WA 392 ms 6244 KiB
test_61.txt WA 336 ms 6324 KiB
test_62.txt WA 585 ms 6264 KiB
test_63.txt WA 408 ms 6232 KiB
test_64.txt WA 493 ms 6252 KiB
test_65.txt WA 430 ms 6304 KiB
test_66.txt WA 655 ms 6328 KiB
test_67.txt WA 720 ms 6380 KiB
test_68.txt WA 642 ms 6232 KiB
test_69.txt WA 243 ms 3732 KiB
test_70.txt WA 272 ms 4924 KiB
test_71.txt WA 407 ms 3760 KiB
test_72.txt WA 232 ms 5968 KiB
test_73.txt WA 300 ms 5008 KiB
test_74.txt WA 196 ms 5528 KiB
test_75.txt WA 277 ms 4652 KiB
test_76.txt WA 687 ms 4492 KiB
test_77.txt WA 263 ms 6312 KiB
test_78.txt WA 254 ms 6400 KiB
test_79.txt WA 463 ms 6252 KiB
test_80.txt WA 270 ms 6468 KiB
test_81.txt WA 296 ms 6336 KiB
test_82.txt WA 401 ms 6216 KiB
test_83.txt WA 263 ms 6404 KiB
test_84.txt WA 475 ms 6328 KiB