結果

問題 No.1054 Union add query
ユーザー 👑 rin204rin204
提出日時 2022-12-25 18:37:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 2,761 bytes
コンパイル時間 2,214 ms
コンパイル使用メモリ 211,368 KB
実行使用メモリ 16,972 KB
最終ジャッジ日時 2024-11-19 08:21:42
合計ジャッジ時間 5,052 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 133 ms
6,820 KB
testcase_04 AC 168 ms
16,736 KB
testcase_05 AC 130 ms
6,816 KB
testcase_06 AC 135 ms
8,576 KB
testcase_07 AC 124 ms
8,576 KB
testcase_08 AC 131 ms
8,576 KB
testcase_09 AC 163 ms
16,972 KB
testcase_10 AC 96 ms
16,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "A.cpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n"

void print(){
	cout << '\n';
}

template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
	cout << head;
	if (sizeof...(Tail)) cout << ' ';
  	print(forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> &A){
	int n = A.size();
	for(int i = 0; i < n; i++){
		cout << A[i];
		if(i == n - 1) cout << '\n';
		else cout << ' ';
	}
}

template<typename T, typename S>
void prisep(vector<T> &A, S sep){
	int n = A.size();
	for(int i = 0; i < n; i++){
		cout << A[i];
		if(i == n - 1) cout << '\n';
		else cout << sep;
	}
}

template<typename T>
void print(vector<vector<T>> &A){
	for(auto &row: A) print(row);
}

#line 3 "Library/C++/data_structure/WeightedUnionFind.hpp"
using namespace std;

template<typename T>
struct WeightedUnionFind{
    int n;
    vector<int> par;
    vector<T> D;
    vector<T> W;
    int group;

    WeightedUnionFind(int n, vector<T> W) : n(n), W(W){
        par.assign(n, -1);
        group = n;
        D.assign(n, T(0));
    }

    WeightedUnionFind(int n): WeightedUnionFind(n, vector<T>(n, T(0))) {}

    int find(int x){
        if(par[x] < 0) return x;
        int p = find(par[x]);
        D[x] += D[par[x]];
        par[x] = find(p);
        return p;
    }

    bool unite(int x, int y, T d){
        // x = y + d
        int xp = find(x);
        int yp = find(y);
        d -= D[x];
        x = xp;
        d += D[y];
        y = yp;
        if(x == y){
            assert(d == 0);
            return false;
        }
        if(par[x] > par[y]){
            swap(x, y);
            d *= -1;
        }
        group--;
        par[x] += par[y];
        D[y] = -d;
        par[y] = x;
        return true;
    }

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

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

    vector<int> roots(){
        vector<int> ret;
        for(int i = 0; i < n; i++){
            if(i == find(i)) ret.push_back(i);
        }
        return ret;
    }

    T diff(int x, int y){
        assert(same(x, y));
        return D[x] - D[y];
    }

    void all_add(int a, T b){
        a = find(a);
        W[a] += b;
    }
    
    T get(int a){
        int p = find(a);
        return W[p] + diff(a, p);
    }
};
#line 43 "A.cpp"


void solve(){
	int n, Q;
	cin >> n >> Q;
	int t, a, b;
	WeightedUnionFind<ll> UF(n);
	while(Q--){
		cin >> t >> a >> b;
		a--;
		if(t == 1){
			b--;
			UF.unite(a, b, UF.get(a) - UF.get(b));
		}
		else if(t == 2){
			UF.all_add(a, b);
		}
		else{
			print(UF.get(a));
		}
	}
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    t = 1;
    // cin >> t;
    while(t--) solve();
	return 0;
}
0