結果

問題 No.1054 Union add query
ユーザー kappybarkappybar
提出日時 2020-05-15 22:43:30
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 2,263 bytes
コンパイル時間 1,943 ms
コンパイル使用メモリ 171,892 KB
実行使用メモリ 9,160 KB
最終ジャッジ日時 2023-10-19 15:47:20
合計ジャッジ時間 4,424 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 159 ms
4,672 KB
testcase_04 AC 213 ms
9,160 KB
testcase_05 AC 151 ms
4,348 KB
testcase_06 AC 155 ms
5,728 KB
testcase_07 AC 137 ms
5,728 KB
testcase_08 AC 151 ms
5,728 KB
testcase_09 AC 203 ms
9,160 KB
testcase_10 AC 110 ms
9,160 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;


struct potential_Unionfind{
    vector<int> parents;
    vector<int> weights;
    int m;
    potential_Unionfind(int n):parents(n,-1){
        m = n;
        weights.resize(n);
    }

    int find(int x){
        if(parents[x] < 0) return x;
        else{
            int p = find(parents[x]);
            weights[x] += weights[parents[x]];
            return parents[x] = p;
        }
    }

    //weight[y] - weights[x] = wとなるようにuniteする。
    bool unite(int x,int y,int w){
        w += weight(x);
        w -= weight(y);
        x = find(x);
        y = find(y);
        if(x == y) return false;//もうすでに繋がれている頂点ならfalseを返す
        if(parents[x] > parents[y]) {swap(x,y); w = -w;}
        parents[x] += parents[y];
        parents[y] = x;
        weights[y] = w;
        return true;
    }

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

    //weightsは各頂点から根までの距離
    int weight(int x){
        find(x);
        return weights[x];
    }

    //まずsame(x,y)で繋がっているかわからないと正しい答えは出てこない
    int diff(int x,int y){
         return weight(y) - weight(x);
    }

};

int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    //cin >> n >> q;
    potential_Unionfind uf(n);
    vector<int> sum(n,0);
    rep(i,q){
        int t,a,b;
        scanf("%d %d %d",&t,&a,&b);
        //cin >> t >> a >> b;
        if(t==1){
            --a;--b;
            int k = uf.find(a);
            int ka = sum[k] + uf.diff(k,a);
            int l = uf.find(b);
            int lb = sum[l] + uf.diff(l,b);
            uf.unite(a,b,lb-ka);
        }else if(t==2){
            --a;
            sum[uf.find(a)] += b;
        }else if(t==3){
            --a;
            int p = uf.find(a);
            printf("%d \n",sum[p] + uf.diff(p,a));
            //cout << sum[p] + uf.diff(p,a)<< endl ;
            //cout << uf.diff(p,a) << endl;
        }
    }

    return 0;
}
0