結果

問題 No.1054 Union add query
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-05-21 14:46:41
言語 TypeScript
(5.4.3)
結果
TLE  
実行時間 -
コード長 3,992 bytes
コンパイル時間 7,987 ms
コンパイル使用メモリ 230,444 KB
実行使用メモリ 110,848 KB
最終ジャッジ日時 2024-12-31 16:49:54
合計ジャッジ時間 24,199 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
40,064 KB
testcase_01 AC 69 ms
40,192 KB
testcase_02 AC 69 ms
39,936 KB
testcase_03 AC 1,927 ms
100,348 KB
testcase_04 AC 1,925 ms
110,848 KB
testcase_05 AC 1,870 ms
98,428 KB
testcase_06 AC 1,930 ms
106,140 KB
testcase_07 AC 1,799 ms
105,232 KB
testcase_08 AC 1,551 ms
106,592 KB
testcase_09 TLE -
testcase_10 AC 761 ms
108,348 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