Submission #3369669


Source Code Expand

import strutils
import sequtils
import algorithm
import math
import queues
import tables
import sets
import logging
import future

const INF* = int(1e18 + 373)

proc readSeq*(): seq[string] = stdin.readLine().strip().split()
proc readSeq*(n: Natural): seq[string] =
  result = newSeq[string](n)
  for i in 0..<n:
    result[i] = stdin.readLine().strip()

proc readInt1*(): int = readSeq().map(parseInt)[0]
proc readInt2*(): (int, int) =
  let a = readSeq().map(parseInt)
  return (a[0], a[1])
proc readInt3*(): (int, int, int) =
  let a = readSeq().map(parseInt)
  return (a[0], a[1], a[2])
proc readInt4*(): (int, int, int, int) =
  let a = readSeq().map(parseInt)
  return (a[0], a[1], a[2], a[3])

type seq2*[T] = seq[seq[T]]
proc newSeq2*[T](n1, n2: Natural): seq2[T] = newSeqWith(n1, newSeq[T](n2))

#------------------------------------------------------------------------------#
type UnionFindTree = tuple[ p, h, w: seq[int] ]

proc initUnionFindTree(n: int): UnionFindTree =
  var p = newSeq[int](n)
  p.fill(-1)
  var h = newSeq[int](n)
  h.fill(0)
  var w = newSeq[int](n)
  w.fill(1)
  return (p, h, w)

proc find(this: var UnionFindTree, v: int): int =
  if this.p[v] == -1:
    return v
  this.p[v] = find(this, this.p[v])
  return this.p[v]

proc same(this: var UnionFindTree, u, v: int): bool =
  this.find(u) == this.find(v)

proc union(this: var UnionFindTree, u, v: int) =
  let uRoot = this.find(u)
  let vRoot = this.find(v)
  if uRoot == vRoot:
    return

  if this.h[uRoot] > this.h[vRoot]:
    this.p[vRoot] = uRoot
    this.w[uRoot] += this.w[vRoot]
  else:
    this.p[uRoot] = vRoot
    this.w[vRoot] += this.w[uRoot]
    if this.h[uRoot] == this.h[vRoot]:
      this.h[vRoot] += 1

proc reduceL[T1, T2](a: seq[T1]; e: T2; f: (T2, T1) -> T2): T2 =
  var ans = e
  for i in 0..<a.len():
    ans = f(ans, a[i])
  return ans

#------------------------------------------------------------------------------#
type Pred1[T] = T -> bool

# [lb, ub)
proc nibutanLb(lb, ub: int; f: Pred1[int]): int =
  var lb = lb
  var ub = ub
  while ub - lb > 1:
    let mid = (ub + lb) div 2
    if f(mid):
      lb = mid
    else:
      ub = mid
  return lb

# (lb, ub]
proc nibutanUb(lb, ub: int; f: Pred1[int]): int =
  var lb = lb
  var ub = ub
  while ub - lb > 1:
    let mid = (ub + lb) div 2
    if f(mid):
      ub = mid
    else:
      lb = mid
  return ub
#------------------------------------------------------------------------------#

type Edge = tuple [ a, b, c: int ]

proc compareEdgeByWeight(e1, e2: Edge): int =
  if e1.c == e2.c:
    return 0
  elif e1.c > e2.c:
    return 1
  else:
    return -1

proc minimum_spanning_tree(n: int; es: seq[Edge]): seq[Edge] =
  let es = es.sorted(compareEdgeByWeight)

  var uft = initUnionFindTree(n)
  var ans = newSeq[Edge](0)
  for e in es:
    if ans.len() >= n - 1:
      break
    if not uft.same(e.a, e.b):
      ans.add(e)
      uft.union(e.a, e.b)

  return ans

proc buildRootedTree(n: int; es: seq[Edge]): seq[Edge] =
  var g = newSeq2[(int, int)](n, 0)
  for e in es:
    g[e.a].add((e.b, e.c))
    g[e.b].add((e.a, e.c))

  var ans = newSeq[Edge](n)
  var stack = newSeq[int](0)
  var used = newSeq[bool](n)
  stack.add(0)
  used[0] = true
  ans[0] = (0, 0, 0)
  while stack.len() != 0:
    let v = stack.pop()
    for e in g[v]:
      if used[e[0]]:
        continue
      used[e[0]] = true
      stack.add(e[0])
      ans[e[0]] = (e[0], v, e[1])

  return ans

proc parent(pps: seq2[Edge]; v, i: int): int =
  var u = v
  var j = i

  var k = 0
  while j != 0:
    if (j and 1) != 0:
      u = pps[k][u].b
    j = j div 2
    k += 1

  return u

proc parentMaxEdge(pps: seq2[Edge]; v, i: int): int =
  var u = v
  var j = i

  var ans = -1
  var k = 0
  while j != 0:
    if (j and 1) != 0:
      ans = max(ans, pps[k][u].c)
      u = pps[k][u].b
    j = j div 2
    k += 1

  return ans

proc depth(pps: seq2[Edge]; v: int): int =
  nibutanUb(-1, 2^12, it => parent(pps, v, it) == 0)

proc lca(pps: seq2[Edge]; d: seq[int]; v, u: int): int =
  var v = v
  var u = u
  if d[v] < d[u]:
    swap(v, u)
  v = parent(pps, v, d[v] - d[u])
  let diff = nibutanUb(-1, 2^12, it => parent(pps, v, it) == parent(pps, u, it))
  return parent(pps, v, diff)

proc main() =
  let (n, m) = readInt2()

  var es = newSeq[Edge](m)
  for i in 0..<m:
    let (a, b, c) = readInt3()
    es[i] = (a - 1, b - 1, c)

  let q = readInt1()
  var qs = newSeq[(int, int)](q)
  for i in 0..<q:
    let (s, t) = readInt2()
    qs[i] = (s - 1, t - 1)

  let mst = minimum_spanning_tree(n, es)
  let mstSum = mst.reduceL(0, (acc, e) => (acc + e.c))

  let ps = buildRootedTree(n, mst)
  var pps = newSeq2[Edge](13, n)
  pps[0] = ps
  for i in 1..12:
    for v in 0..<n:
      let parent = pps[i - 1][pps[i - 1][v].b].b
      let maxWeight = max(pps[i - 1][v].c, pps[i - 1][pps[i - 1][v].b].c)
      pps[i][v] = (v, parent, maxWeight)

  var d = newSeq[int](n)
  for v in 0..<n:
    d[v] = depth(pps, v)

  for q in qs:
    let a = lca(pps, d, q[0], q[1])
    var ans = 0
    ans = max(ans, parentMaxEdge(pps, q[0], d[q[0]] - d[a]))
    ans = max(ans, parentMaxEdge(pps, q[1], d[q[1]] - d[a]))
    echo mstSum - ans

main()

Submission Info

Submission Time
Task A - Graph
User somq14
Language Nim (0.13.0)
Score 0
Code Size 5398 Byte
Status TLE
Exec Time 3158 ms
Memory 48804 KB

Compile Error

Hint: system [Processing]
Hint: Main [Processing]
Hint: strutils [Processing]
Hint: parseutils [Processing]
Hint: sequtils [Processing]
Hint: algorithm [Processing]
Hint: math [Processing]
Hint: times [Processing]
Hint: queues [Processing]
Hint: tables [Processing]
Hint: hashes [Processing]
Hint: etcpriv [Processing]
Hint: sets [Processing]
Hint: os [Processing]
Hint: posix [Processing]
Hint: logging [Processing]
lib/pure/logging.nim(128, 22) Hint: 'Exception' is declared but not used [XDeclaredButNotUsed]
Hint: future [Processing]
Hint: macros [Processing]
Main.nim(79, 6) Hint: 'Main.nibutanLb(lb: int, ub: int, f: Pred1[system.int])' is declared but not used [XDeclaredButNotUsed]
Hint:  [Link]
Hint: operation successful (25015 lines compiled; 2.793 sec total; 26.266MB; Release Build) [SuccessX]

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 3
TLE × 9
AC × 4
TLE × 17
AC × 6
TLE × 25
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
subtask_1_1.txt AC 8 ms 4220 KB
subtask_1_10.txt TLE 3156 ms 24692 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_2.txt TLE 3155 ms 5128 KB
subtask_1_3.txt TLE 3158 ms 48404 KB
subtask_1_4.txt TLE 3155 ms 5028 KB
subtask_1_5.txt TLE 3155 ms 4744 KB
subtask_1_6.txt TLE 3156 ms 10136 KB
subtask_1_7.txt TLE 3158 ms 48404 KB
subtask_1_8.txt TLE 3155 ms 4656 KB
subtask_1_9.txt TLE 3155 ms 4800 KB
subtask_2_1.txt TLE 3158 ms 48676 KB
subtask_2_2.txt TLE 3157 ms 48572 KB
subtask_2_3.txt TLE 3158 ms 48804 KB
subtask_2_4.txt TLE 3158 ms 48676 KB
subtask_2_5.txt TLE 3155 ms 5140 KB
subtask_2_6.txt TLE 3155 ms 5064 KB
subtask_2_7.txt TLE 3155 ms 10456 KB
subtask_2_8.txt TLE 3158 ms 48804 KB
subtask_3_1.txt TLE 3157 ms 42164 KB
subtask_3_2.txt TLE 3157 ms 42140 KB
subtask_3_3.txt TLE 3156 ms 8976 KB
subtask_3_4.txt TLE 3155 ms 8852 KB
subtask_3_5.txt TLE 3156 ms 22880 KB
subtask_3_6.txt TLE 3157 ms 32436 KB
subtask_3_7.txt TLE 3157 ms 41956 KB
subtask_3_8.txt TLE 3158 ms 42140 KB