結果

問題 No.900 aδδitivee
ユーザー sgsw
提出日時 2021-08-17 19:44:56
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 6,925 bytes
コンパイル時間 11,513 ms
コンパイル使用メモリ 240,516 KB
実行使用メモリ 53,204 KB
最終ジャッジ日時 2024-10-10 18:45:36
合計ジャッジ時間 21,372 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"bufio"
"fmt"
"os"
"reflect"
"strconv"
)
var wg = bufio.NewScanner(os.Stdin)
const (
inf = int(1e18)
initialBufSize = int(1e6)
maxBufSize = int(1e6)
)
var buf []byte = make([]byte, initialBufSize)
type edge struct {
u, v, w int
}
type Graph struct {
n int
edges [][]edge
}
func NewGraph(n int) *Graph {
g := &Graph{
n: n,
edges: make([][]edge, n),
}
for i := 0; i < n; i++ {
g.edges[i] = make([]edge, 0)
}
return g
}
func euler_tour(g *Graph, S int) ([]int, []int, []int, []int) {
DIST, par := make([]int, g.n), make([]int, g.n)
path := make([]int, 0)
for i := 0; i < g.n; i++ {
DIST[i] = inf
par[i] = -1
}
DIST[S] = 0
//
var dfs func(s int)
IN, OUT := make([]int, g.n), make([]int, g.n)
inc := 0
dfs = func(s int) {
path = append(path, s)
IN[s] = inc
for _, e := range g.edges[s] {
if DIST[e.v] == inf {
DIST[e.v] = DIST[s] + e.w
par[e.v] = s
inc++
dfs(e.v)
}
}
inc++
p := par[s]
if p != -1 {
path = append(path, p)
}
OUT[s] = inc
}
dfs(0)
return IN, OUT, DIST, path
}
func main() {
n := nextInt()
g := NewGraph(n)
for i := 0; i < n-1; i++ {
u, v, w := nextInt(), nextInt(), nextInt()
g.edges[u] = append(g.edges[u], edge{u, v, w})
g.edges[v] = append(g.edges[v], edge{v, u, w})
}
//euler_tour
IN, OUT, DIST, Path := euler_tour(g, 0)
seg, _ := Gen(Monoid{}, op_Monoid(0), binary_op, S_Op, S_Ide, F_Op, F_Ide, 2*n-2)
A := make([]Monoid, 2*n-2)
for i := 0; i < 2*n-2; i++ {
if DIST[Path[i]] < DIST[Path[i+1]] {
A[i] = Monoid{cnt: 1, sum: 0}
} else {
A[i] = Monoid{cnt: -1, sum: 0}
}
}
SliceGen(seg, A)
q := nextInt()
for i := 0; i < q; i++ {
switch nextInt() {
case 1:
node, val := nextInt(), nextInt()
seg.Apply(IN[node], OUT[node]-1, op_Monoid(val))
case 2:
node := nextInt()
ans := DIST[node] + seg.Prod(0, IN[node]).sum
fmt.Printf("%d\n", ans)
}
}
}
type Monoid struct {
cnt, sum int
}
func S_Op(x, y Monoid) Monoid {
return Monoid{x.cnt + y.cnt, x.sum + y.sum}
}
func S_Ide() Monoid {
return Monoid{0, 0}
}
////////////////////////////////////////////////////////
//Definition of Monoid F.
type op_Monoid int
func F_Op(x, y op_Monoid) op_Monoid {
return op_Monoid(int(x) + int(y))
}
func F_Ide() op_Monoid {
return op_Monoid(0)
}
////////////////////////////////////////////////////////
//binary opearation S x F -> S
func binary_op(x Monoid, f op_Monoid) Monoid {
return Monoid{x.cnt, x.cnt*int(f) + x.sum}
}
type LazySegTree struct {
monoid_type Monoid
operator_monoid_type op_Monoid
//
op func(Monoid, Monoid) Monoid /* S x S-> S */
e func() Monoid /*identity op of S (value-monoid)*/
//
operator_op func(op_Monoid, op_Monoid) op_Monoid /*f x f -> f*/
operator_e func() op_Monoid /*identity op of F(opearator-monoid)*/
//()
binary_op func(Monoid, op_Monoid) Monoid /* S x F -> S */
d []Monoid
_d []Monoid
_lz []op_Monoid
n int /* size*/
log int
size int
}
func Gen(monoid Monoid, op_monoid op_Monoid, binary_op_monoid func(Monoid, op_Monoid) Monoid, S_op func(Monoid, Monoid) Monoid, S_e func() Monoid,
    F_op func(op_Monoid, op_Monoid) op_Monoid, F_e func() op_Monoid, n int) (LazySegTree, bool) {
seg := LazySegTree{monoid_type: monoid, operator_monoid_type: op_monoid, op: S_op, e: S_e, operator_op: F_op, operator_e: F_e, binary_op:
        binary_op_monoid, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0}
collect := true
switch n > 0 {
case true:
seg.d = make([]Monoid, n)
for i := range seg.d {
seg.d[i] = seg.e()
}
default:
collect = false
return seg, collect
}
seg.n = len(seg.d)
for ord := uint(0); (1 << ord) < seg.n; {
ord++
seg.log = int(ord)
}
seg.size = 1 << uint(seg.log)
seg._d = make([]Monoid, 2*seg.size)
seg._lz = make([]op_Monoid, seg.size)
for i := range seg._d {
seg._d[i] = seg.e()
}
for i := range seg._lz {
seg._lz[i] = seg.operator_e()
}
for i := 0; i < seg.n; i++ {
seg._d[seg.size+i] = seg.d[i]
}
for i := seg.size - 1; i > 0; i-- {
seg._update(i)
}
return seg, collect
}
func SliceGen(seg LazySegTree, array []Monoid) bool {
ok := true
if len(array) != seg.n {
ok = false
return ok
}
for _, v := range array {
if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) {
ok = false
return ok
}
}
for i := 0; i < seg.n; i++ {
seg._d[seg.size+i] = array[i]
}
for i := seg.size - 1; i > 0; i-- {
seg._update(i)
}
return ok
}
func (seg LazySegTree) _update(k int) {
seg._d[k] = seg.op(seg._d[2*k], seg._d[2*k+1])
}
func (seg LazySegTree) _all_apply(k int, f op_Monoid) {
seg._d[k] = seg.binary_op(seg._d[k], f)
if k < seg.size {
seg._lz[k] = seg.operator_op(seg._lz[k], f)
}
}
func (seg LazySegTree) _push(k int) {
seg._all_apply(k<<1, seg._lz[k])
seg._all_apply((k<<1)+1, seg._lz[k])
seg._lz[k] = seg.operator_e()
}
func (seg LazySegTree) Set(p int, x Monoid) {
//a[p] -> x in O(logN).
p += seg.size
for i := uint(seg.log); i > 0; i-- {
seg._push(p >> i)
}
seg._d[p] = x
for i := uint(1); i <= uint(seg.log); i++ {
seg._update(p >> i)
}
}
func (seg LazySegTree) Get(p int) Monoid {
// a[p] in O(logN).
p += seg.size
for i := uint(seg.log); i > 0; i-- {
seg._push(p >> i)
}
return seg._d[p]
}
func (seg LazySegTree) GetThemAll() []Monoid {
//get all element in O(N).
for i := 0; i < seg.size; i++ {
seg._push(i)
}
a := make([]Monoid, seg.n)
for i := 0; i < seg.n; i++ {
a[i] = seg._d[i+seg.size]
}
return a
}
func (seg LazySegTree) Prod(l, r int) Monoid {
//a[l..r) in O(logN).
sml := seg.e()
smr := seg.e()
l += seg.size
r += seg.size
for i := uint(seg.log); i > 0; i-- {
if (l>>i)<<i != l {
seg._push(l >> i)
}
if (r>>i)<<i != r {
seg._push(r >> i)
}
}
for l < r {
if l&1 == 1 {
sml = seg.op(sml, seg._d[l])
l++
}
if r&1 == 1 {
r--
smr = seg.op(seg._d[r], smr)
}
l >>= 1
r >>= 1
}
return seg.op(sml, smr)
}
func (seg LazySegTree) AllProd() Monoid {
return seg._d[1]
}
func (seg LazySegTree) Apply(l, r int, f op_Monoid) {
// a[l..r) -> f(a[l..r)) in O(logN).
l += seg.size
r += seg.size
for i := uint(seg.log); i > 0; i-- {
if (l>>i)<<i != l {
seg._push(l >> i)
}
if (r>>i)<<i != r {
seg._push((r - 1) >> i)
}
}
l2, r2 := l, r
for l < r {
if l&1 == 1 {
seg._all_apply(l, f)
l++
}
if r&1 == 1 {
r--
seg._all_apply(r, f)
}
l >>= 1
r >>= 1
}
l, r = l2, r2
for i := uint(1); i <= uint(seg.log); i++ {
if (l>>i)<<i != l {
seg._update(l >> i)
}
if (r>>i)<<i != r {
seg._update((r - 1) >> i)
}
}
}
func init() {
wg.Split(bufio.ScanWords)
wg.Buffer(buf, maxBufSize)
}
func nextInt() int {
wg.Scan()
i, e := strconv.Atoi(wg.Text())
if e != nil {
panic(e)
}
return i
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0