ARC036 D 偶数メートル

問題ページ

解法

2つの街が直接偶数メートルで繋がっているか、2つの街の両方から行き来できる奇数長の閉路があれば、またその時に限りクエリに対する出力はYESとなる。これは、重み付き（ポテンシャル付き）Union-Find木を使うと調べることができる。道路を繋ぐとき、もともと繋がっていない場合はそのまま繋ぐ。繋がっていた場合、その間の距離と新しい道路の距離の和が奇数であれば、奇数長の閉路ができることになる。奇数長の閉路があるかどうかをbool配列で管理しておくことによって、この問題を解くことができる。

実装

提出コード - https://atcoder.jp/contests/arc036/submissions/6435962
重み付きUF - https://github.com/mhrb-minase/competitive_programming/blob/master/DataStructure/UnionFind.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;

class UnionFind{
    vector<int> par;
    vector<long long> wei;
    int groupCount;

public:
    UnionFind(int n = 0){
        init(n);
    }

    void init(int n = 0){
        par.resize(n);
        fill(par.begin(), par.end(), -1);

        wei.resize(n);
        fill(wei.begin(), wei.end(), 0LL);

        groupCount = n;

        return;
    }

    int root(int x){
        if(par[x] < 0){
            return x;
        }
        int r = root(par[x]);
        wei[x] += wei[par[x]];
        return par[x] = r;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int size(int x){
        return -par[root(x)];
    }

    long long weight(int x){
        root(x);
        return wei[x];
    }

    long long diff(int x, int y){
        return weight(y) - weight(x);
    }

    bool unite(int x, int y, long long w = 0){
        w += weight(x) - weight(y);

        x = root(x);
        y = root(y);

        if(x == y){
            return false;
        }

        if(par[y] < par[x]){
            swap(x, y);
            w = -w;
        }

        par[x] += par[y];
        par[y] = x;
        wei[y] = w;
        --groupCount;

        return true;
    }

    int size(void){
        return groupCount;
    }
};

int main(){
    int n, q;
    cin >> n >> q;

    UnionFind uf(n);
    vector<bool> v(n, false);

    while(q--){
        int w, x, y;
        long long z;
        cin >> w >> x >> y >> z;
        --x;
        --y;
        if(w == 1){
            if(uf.same(x, y)){
                if(abs(uf.diff(x, y)) % 2LL != z % 2LL){
                    v[uf.root(x)] = true;
                }
            }else{
                bool flag = v[uf.root(x)] || v[uf.root(y)];
                uf.unite(x, y, z);
                v[uf.root(x)] = flag;
            }
        }else{
            if(uf.same(x, y) && (abs(uf.diff(x, y)) % 2LL == 0LL || v[uf.root(x)])){
                cout << "YES" << endl;
            }else{
                cout << "NO" << endl;
            }
        }
    }

    return 0;
}