Submission #1770165

---

Source Code Expand

#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
lli MOD = 1000000007;
#define UF_MAX 200005
struct ufind {
    int par[UF_MAX];
    int rank[UF_MAX];
    int count[UF_MAX];
    ufind(int n)
    {
        rep(i, n)
        {
            par[i] = i;
            rank[i] = 0;
            count[i] = 1;
        }
    }
    int find(int x)
    {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y])
                rank[x]++;
        }
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;
    int t, a, b, c;
    ufind uf(2 * n);
    rep(i, q)
    {
        cin >> t >> a >> b >> c;
        c %= 2;
        a--, b--;
        if (t == 1) {
            if (c) {
                uf.unite(a, n + b);
                uf.unite(b, n + a);
            } else {
                uf.unite(a, b);
                uf.unite(n + a, n + b);
            }
        } else {
            if (uf.same(a, b)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
}

Submission Info

Judge Result