結果

問題 No.1054 Union add query
ユーザー niuezniuez
提出日時 2020-05-16 21:33:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 2,638 bytes
コンパイル時間 2,431 ms
コンパイル使用メモリ 180,880 KB
実行使用メモリ 10,016 KB
最終ジャッジ日時 2024-09-22 19:23:52
合計ジャッジ時間 3,935 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,652 KB
testcase_01 AC 3 ms
7,524 KB
testcase_02 AC 3 ms
7,652 KB
testcase_03 AC 26 ms
8,164 KB
testcase_04 AC 28 ms
8,164 KB
testcase_05 AC 23 ms
10,016 KB
testcase_06 AC 23 ms
8,544 KB
testcase_07 AC 19 ms
8,552 KB
testcase_08 AC 20 ms
8,168 KB
testcase_09 AC 24 ms
8,420 KB
testcase_10 AC 14 ms
7,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")

#include <vector>
#include <tuple>
#include <iostream>
#include <bits/stdc++.h>
using ll = long long;

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	int pn = 1;
	if (*ci == '-') {
		pn = -pn;
		ci++;
	}
	ll tmp = *(ll*)ci;
	int dig = ((tmp & ma0) ^ ma0) ? 68 - __builtin_ctzll((tmp & ma0) ^ ma0) : 0;
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += (72 - dig >> 3);
	return pn * tmp;
}
const int dm = 1 << 22;
char dn[dm], * di = dn;
inline void putint(int X) {
	if (X == 0) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	if (X < 0) {
		*di++ = '-';
		X = -X;
	}
	int keta = 0;
	char C[20];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

int par[505050];
int Sigma[505050];

struct union_find {
  union_find(int N) {
    std::fill(std::begin(par), std::end(par), -1);
  }
  int root(int x) {
    if(par[x] < 0) {
      return x;
    }
    int v = x;
    while(par[par[v]] >= 0) {
      v = par[v];
      Sigma[x] += Sigma[v];
    }
    par[x] = par[v];
    return par[v];
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return;
    if(par[x] > par[y]) std::swap(x, y);
    par[x] += par[y];
    par[y] = x;
    Sigma[y] -= Sigma[x];
    return;
  }
  void add(int v, int a) {
    Sigma[root(v)] += a;
  }
  int value(int v) {
    int r = root(v);
    if(r == v) {
      return Sigma[v];
    }
    else {
      return Sigma[v] + Sigma[r];
    } 
  }
};

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int N = getint(), Q = getint();

  union_find uf(N);
  while(Q--) {
    int t = getint(), a = getint(), b = getint();
    a--;
    if(t == 1) {
      b--;
      uf.unite(a, b);
    }
    else if(t == 2) {
      uf.add(a, b);
    }
    else {
      putint(uf.value(a));
    }
    /*
    cout << Q << endl;
    rep(i,0,N) {
      cout << i << " = " << uf.Sigma[i] << " " << uf.par[i] << endl;
    }*/
  }
  fwrite(dn, 1, di - dn, stdout);
}
0