Approach
Stack-based processing
For Codeforces 1076D — Edge Deletion, the implementation keeps unresolved items in last-in, first-out order, often to match boundaries, parse structure, or maintain monotonic candidates.
- Define what every stack entry represents.
- Pop entries once the current item resolves or invalidates them.
- Push the current item with only the information later steps need.
Code notes
- 99 lines of Go from the credited upstream file 1076D.go.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
If each item is pushed and popped at most once, the stack work is linear.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1package main2 3import (4 "bufio"5 "container/heap"6 . "fmt"7 "io"8)9 1011type pr76 struct {12 v int13 d int6414}15type hp76 []pr7616 17func (h hp76) Len() int { return len(h) }18func (h hp76) Less(i, j int) bool { return h[i].d < h[j].d }19func (h hp76) Swap(i, j int) { h[i], h[j] = h[j], h[i] }20func (h *hp76) Push(v interface{}) { *h = append(*h, v.(pr76)) }21func (h *hp76) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }22func (h *hp76) push(v pr76) { heap.Push(h, v) }23func (h *hp76) pop() pr76 { return heap.Pop(h).(pr76) }24 25func CF1076D(_r io.Reader, _w io.Writer) {26 in := bufio.NewReader(_r)27 out := bufio.NewWriter(_w)28 defer out.Flush()29 30 var n, m, up, v, w, wt int31 Fscan(in, &n, &m, &up)32 type neighbor struct{ to, wt, i int }33 g := make([][]neighbor, n)34 for i := 1; i <= m; i++ {35 Fscan(in, &v, &w, &wt)36 v--37 w--38 g[v] = append(g[v], neighbor{w, wt, i})39 g[w] = append(g[w], neighbor{v, wt, i})40 }41 42 type pair struct{ f, i int }43 fa := make([]pair, n)44 const inf int64 = 1e1845 dist := make([]int64, n)46 for i := range dist {47 dist[i] = inf48 }49 dist[0] = 050 q := hp76{{}}51 for len(q) > 0 {52 p := q.pop()53 v := p.v54 if dist[v] < p.d {55 continue56 }57 for _, e := range g[v] {58 w := e.to59 if newD := dist[v] + int64(e.wt); newD < dist[w] {60 dist[w] = newD61 fa[w] = pair{v, e.i} 62 q.push(pr76{w, newD})63 }64 }65 }66 67 68 deg := make([]int, n)69 for _, p := range fa {70 deg[p.f]++71 }72 ans := []interface{}{}73 q2 := []int{}74 for i, d := range deg {75 if d == 0 {76 q2 = append(q2, i)77 }78 }79 for len(q2) > 0 {80 p := fa[q2[0]]81 q2 = q2[1:]82 ans = append(ans, p.i)83 if p.f == 0 {84 continue85 }86 w := p.f87 if deg[w]--; deg[w] == 0 {88 q2 = append(q2, w)89 }90 }91 if len(ans) > up {92 ans = ans[len(ans)-up:]93 }94 Fprintln(out, len(ans))95 Fprintln(out, ans...)96}97 9899