結果
問題 | No.900 aδδitivee |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
package mainimport ("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 intedges [][]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] = infpar[i] = -1}DIST[S] = 0//再帰関数var dfs func(s int)IN, OUT := make([]int, g.n), make([]int, g.n)inc := 0dfs = func(s int) {path = append(path, s)IN[s] = incfor _, e := range g.edges[s] {if DIST[e.v] == inf {DIST[e.v] = DIST[s] + e.wpar[e.v] = sinc++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_tourIN, 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]).sumfmt.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 intfunc 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 -> Sfunc binary_op(x Monoid, f op_Monoid) Monoid {return Monoid{x.cnt, x.cnt*int(f) + x.sum}}type LazySegTree struct {monoid_type Monoidoperator_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_Monoidn int /* size*/log intsize 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 := trueswitch n > 0 {case true:seg.d = make([]Monoid, n)for i := range seg.d {seg.d[i] = seg.e()}default:collect = falsereturn 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 := trueif len(array) != seg.n {ok = falsereturn ok}for _, v := range array {if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) {ok = falsereturn 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.sizefor i := uint(seg.log); i > 0; i-- {seg._push(p >> i)}seg._d[p] = xfor 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.sizefor 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.sizer += seg.sizefor 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 >>= 1r >>= 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.sizer += seg.sizefor 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, rfor l < r {if l&1 == 1 {seg._all_apply(l, f)l++}if r&1 == 1 {r--seg._all_apply(r, f)}l >>= 1r >>= 1}l, r = l2, r2for 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}