Submission #68774278

---

Source Code Expand

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <tuple>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using ll = long long;
using ld = long double;
using namespace std;
#define endl "\n";
#define ff first
#define ss second

#define forn(i,n) for(int i=0;i<n;i++)
#define dbgv(v) cout<<#v<<" "<<v<<endl
#define dbga(a,n) forn(i,n-1) {cout<<a[i]<<' ';} cout<<a[n-1]<<'\n';
#define all(v) (v).begin(), (v).end()

const int N=3e5;
int parent[N];
int c[N];
int sc[N];
int sz[N];


int find_set(int v) {
    if (v == parent[v])
        return v;
    return find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b){
        if (sz[a] < sz[b]){
            swap(a, b);
        }            
        sz[a] += sz[b];
        sc[a]+=sc[find_set(b)];
        parent[b] = a;
    }
}

void solve(){
    forn(i,N){
        parent[i]=i;
    }
    forn(i,N){
        c[i]=0;
        sc[i]=0;
        sz[i]=1;
    }
    int n,q;
    cin>>n>>q;
    
    forn(i,q){
        int x;
        cin>>x;
        if(x==1){
            int u,v;
            cin>>u>>v;
            union_sets(u,v);
        } else if(x==2){
            int v;
            cin>>v;
            if(c[v]){
                c[v]^=1;
                sc[find_set(v)]-=1;
            } else {
                c[v]^=1;
                sc[find_set(v)]+=1; 
            }
        } else {
            int v;
            cin>>v;
            if(sc[find_set(v)]>0){
                cout<<"Yes"<<endl;
            } else{
                cout<<"No"<<endl;
            }
        }
    }
}

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

    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Submission Info

Judge Result