結果

問題 No.900 aδδitivee
ユーザー sgswsgsw
提出日時 2021-08-17 19:52:23
言語 Go
(1.22.1)
結果
AC  
実行時間 343 ms / 2,000 ms
コード長 6,936 bytes
コンパイル時間 10,717 ms
コンパイル使用メモリ 237,712 KB
実行使用メモリ 53,376 KB
最終ジャッジ日時 2024-04-19 02:22:21
合計ジャッジ時間 19,763 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 332 ms
35,968 KB
testcase_08 AC 326 ms
35,840 KB
testcase_09 AC 324 ms
35,200 KB
testcase_10 AC 329 ms
35,840 KB
testcase_11 AC 325 ms
35,840 KB
testcase_12 AC 320 ms
35,840 KB
testcase_13 AC 319 ms
35,200 KB
testcase_14 AC 322 ms
35,840 KB
testcase_15 AC 324 ms
35,968 KB
testcase_16 AC 313 ms
35,840 KB
testcase_17 AC 322 ms
35,968 KB
testcase_18 AC 320 ms
35,840 KB
testcase_19 AC 326 ms
35,200 KB
testcase_20 AC 343 ms
35,840 KB
testcase_21 AC 329 ms
35,968 KB
testcase_22 AC 318 ms
53,248 KB
testcase_23 AC 324 ms
53,248 KB
testcase_24 AC 323 ms
53,376 KB
testcase_25 AC 317 ms
51,148 KB
testcase_26 AC 323 ms
53,248 KB
testcase_27 AC 320 ms
53,376 KB
testcase_28 AC 315 ms
53,192 KB
権限があれば一括ダウンロードができます

ソースコード

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, []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, par
}

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, Par := 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 Par[Path[i+1]] == Path[i] {
			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
}
0