Submission #1059212

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);++i)
#define rep2(i,a,b) for (int i=(a);i<(b);++i)
#define rrep(i,n) for (int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;--i)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) cout<<(#_v)<<":";for(auto(_x):(_v)){cout<<" "<<(_x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

class UnionFind {
private:
    const int n;
    vector<int> uni;
public:
    UnionFind(int _n) : n(_n), uni(_n, -1) {}
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
        return true;
    }
    int getSize(int x) {
        return -uni[root(x)];
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    vector<Pii> edges;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges.emplace_back(a, b);
    }

    vector<bool> alive(m, true);
    vector<vector<int>> queries;
    rep(i, k) {
        int t;
        cin >> t;
        if (!t) {
            int e;
            cin >> e;
            e--;
            queries.emplace_back(vector<int>{t, e});
            alive[e] = false;
        }
        else {
            int a, b;
            cin >> a >> b;
            a--; b--;
            queries.emplace_back(vector<int>{t, a, b});
        }
    }
    reverse(all(queries));

    UnionFind uf(n);
    rep(i, m) {
        if (alive[i]) {
            uf.unite(edges[i].first, edges[i].second);
        }
    }

    vector<string> ans;
    for (auto q : queries) {
        if (!q[0]) {
            uf.unite(edges[q[1]].first, edges[q[1]].second);
        }
        else {
            ans.emplace_back(uf.same(q[1], q[2]) ? "YES" : "NO");
        }
    }
    reverse(all(ans));

    for (auto s : ans) {
        cout << s << endl;
    }
}

Submission Info

Judge Result