結果

問題 No.1054 Union add query
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-05-21 14:50:50
言語 TypeScript
(5.4.3)
結果
TLE  
実行時間 -
コード長 3,993 bytes
コンパイル時間 7,281 ms
コンパイル使用メモリ 258,368 KB
実行使用メモリ 144,376 KB
最終ジャッジ日時 2023-08-23 15:09:00
合計ジャッジ時間 23,476 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
42,312 KB
testcase_01 AC 79 ms
42,340 KB
testcase_02 AC 79 ms
42,260 KB
testcase_03 AC 1,994 ms
124,472 KB
testcase_04 TLE -
testcase_05 AC 1,936 ms
124,016 KB
testcase_06 AC 1,856 ms
132,452 KB
testcase_07 AC 1,711 ms
130,852 KB
testcase_08 AC 1,512 ms
131,848 KB
testcase_09 TLE -
testcase_10 AC 823 ms
132,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 维护分量和的并查集
//
// Union Find Data Structure
//
// Description:
//   An union-find data structure (aka. disjoint set data structure)
//   maintains a disjoint sets and supports the following operations.
//   - unite(u, v): merge sets containing u and v.
//   - find(u, v) : return true if u and v are in the same set
//   - size(u)    : size of the set containing u.
//
//   The weighted version additionally maintains the values for the
//   elements and supports the following operations:
//   - add(u, a)   : value[u] += a
//   - addSet(u, a): value[v] += a for v in set(u)
//   - get(u)      : return value[u]
//   - getSet(u)   : return sum(value[v] for v in set(u))
//
// Complexity:
//   Amortized O(a(n)) for all operations.
//   Here, a(n) is the inverse Ackermann function, which is
//   less than five for a realistic size input.
//
// Verified:
//   AOJ1330 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330
//   and other many problems.
//
import * as fs from 'fs'
import { resolve } from 'path'


class WeightedUnionFind {
  private readonly _parent: Int32Array
  private readonly _value: number[]
  private readonly _delta: number[]
  private readonly _total: number[]
  private _part: number

  constructor(n: number) {
    this._parent = new Int32Array(n).fill(-1)
    this._value = Array(n).fill(0)
    this._delta = Array(n).fill(0)
    this._total = Array(n).fill(0)
    this._part = n
  }

  /**
   * u的值加上delta.
   */
  add(u: number, delta: number): void {
    this._value[u] += delta
    this._total[this.find(u)] += delta
  }

  /**
   * u所在集合的值加上delta.
   */
  addGroup(u: number, delta: number): void {
    const root = this.find(u)
    this._delta[root] += delta
    this._total[root] -= this._parent[root] * delta
  }

  /**
   * u的值.
   */
  get(u: number): number {
    return this._value[u] + this._find(u)[1]
  }

  /**
   * u所在集合的值.
   */
  getGroup(u: number): number {
    return this._total[this.find(u)]
  }

  union(u: number, v: number, f?: (big: number, small: number) => void): boolean {
    u = this.find(u)
    v = this.find(v)
    if (u === v) return false
    if (this._parent[u] > this._parent[v]) {
      u ^= v
      v ^= u
      u ^= v
    }
    this._parent[u] += this._parent[v]
    this._parent[v] = u
    this._delta[v] -= this._delta[u]
    this._total[u] += this._total[v]
    this._part--
    f && f(u, v)
    return true
  }

  find(u: number): number {
    return this._find(u)[0]
  }

  isConnected(u: number, v: number): boolean {
    return this.find(u) === this.find(v)
  }

  getSize(u: number): number {
    return -this._parent[this.find(u)]
  }

  getGroups(): Map<number, number[]> {
    const groups = new Map<number, number[]>()
    for (let i = 0; i < this._parent.length; ++i) {
      const root = this.find(i)
      if (groups.has(root)) {
        groups.get(root)!.push(i)
      } else {
        groups.set(root, [i])
      }
    }
    return groups
  }

  get part(): number {
    return this._part
  }

  private _find(u: number): [root: number, delta: number] {
    if (this._parent[u] < 0) return [u, this._delta[u]]
    let [a, b] = this._find(this._parent[u])
    b += this._delta[u]
    this._parent[u] = a
    this._delta[u] = b - this._delta[a]
    return [a, b]
  }
}



function useInput(path?: string) {
  let data: string
  if (path) {
    data = fs.readFileSync(resolve(__dirname, path), 'utf8')
  } else {
    data = fs.readFileSync(process.stdin.fd, 'utf8')
  }

  const lines = data.split(/\r\n|\r|\n/)
  let lineId = 0
  const input = (): string => lines[lineId++]

  return {
    input
  }
}

const { input } = useInput()
const [n, q] = input().split(' ').map(Number)
const uf = new WeightedUnionFind(n)
for (let i = 0; i < q; ++i) {
  const [op, a, b] = input().split(' ').map(Number)
  if (op === 1) {
    uf.union(a - 1, b - 1)
  } else if (op === 2) {
    uf.addGroup(a - 1, b)
  } else {
    console.log(uf.get(a - 1))
  }
}
0