結果
問題 | No.1640 簡単な色塗り |
ユーザー | 草苺奶昔 |
提出日時 | 2024-09-13 02:54:43 |
言語 | Go (1.22.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,465 bytes |
コンパイル時間 | 14,307 ms |
コンパイル使用メモリ | 219,312 KB |
実行使用メモリ | 20,336 KB |
最終ジャッジ日時 | 2024-09-13 02:55:11 |
合計ジャッジ時間 | 28,504 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 176 ms
20,336 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 23 ms
6,944 KB |
testcase_31 | AC | 178 ms
16,208 KB |
testcase_32 | AC | 159 ms
14,100 KB |
testcase_33 | AC | 103 ms
9,936 KB |
testcase_34 | AC | 131 ms
12,032 KB |
testcase_35 | AC | 107 ms
9,936 KB |
testcase_36 | AC | 23 ms
6,944 KB |
testcase_37 | AC | 33 ms
6,940 KB |
testcase_38 | AC | 165 ms
16,216 KB |
testcase_39 | AC | 64 ms
7,748 KB |
testcase_40 | AC | 65 ms
7,824 KB |
testcase_41 | AC | 134 ms
12,072 KB |
testcase_42 | AC | 76 ms
9,992 KB |
testcase_43 | AC | 77 ms
9,992 KB |
testcase_44 | AC | 82 ms
9,996 KB |
testcase_45 | AC | 58 ms
7,752 KB |
testcase_46 | AC | 26 ms
6,940 KB |
testcase_47 | AC | 17 ms
6,944 KB |
testcase_48 | AC | 163 ms
14,108 KB |
testcase_49 | AC | 8 ms
6,940 KB |
testcase_50 | AC | 2 ms
6,940 KB |
testcase_51 | AC | 2 ms
6,944 KB |
testcase_52 | WA | - |
testcase_53 | WA | - |
07_evil_01.txt | WA | - |
07_evil_02.txt | WA | - |
ソースコード
package main import ( "bufio" "fmt" "os" ) func main() { yuki1640() } // No.1640 簡単な色塗り // https://yukicoder.me/problems/no/1640 // 给定n个点和n对条件,每个条件形如(u,v),表示选择u或v中的一个点。 // 问能否选出所有点. // 如果能,输出选择方案. // // 对每个联通分量,首先需要满足`顶点数等于边数`. // 然后,有两种情况: // - 有自环 // - 有环 func yuki1640() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int32 fmt.Fscan(in, &n) pairs := make([][2]int32, n) for i := range pairs { fmt.Fscan(in, &pairs[i][0], &pairs[i][1]) pairs[i][0]-- pairs[i][1]-- } selects, ok := SelectOneFromEachPairRestore(n, pairs) if !ok { fmt.Fprintln(out, "No") return } fmt.Fprintln(out, "Yes") for _, v := range selects { fmt.Fprintln(out, v+1) } } // SelectOneFromEachEdgeRestore. func SelectOneFromEachPairRestore(n int32, pairs [][2]int32) (selects []int32, ok bool) { graph, deg := make([][][3]int32, n), make([]int32, n) for i := int32(0); i < n; i++ { u, v := pairs[i][0], pairs[i][1] graph[u] = append(graph[u], [3]int32{u, v, i}) graph[v] = append(graph[v], [3]int32{v, u, i}) deg[u]++ deg[v]++ } type E = [2]int32 // (deg,v) pq := NewHeap(func(a, b E) bool { return a[0] > b[0] }, nil) for i := int32(0); i < n; i++ { pq.Push(E{deg[i], i}) } m := int32(len(pairs)) selects = make([]int32, m) for i := int32(0); i < m; i++ { selects[i] = -1 } visited := make([]bool, n) for pq.Len() > 0 { item := pq.Pop() curD, cur := item[0], item[1] if deg[cur] != curD { continue } if visited[cur] { continue } for _, e := range graph[cur] { from, to, id := e[0], e[1], e[2] if selects[id] != -1 { continue } selects[id] = cur visited[cur] = true deg[from]-- deg[to]-- pq.Push(E{deg[from], from}) pq.Push(E{deg[to], to}) break } } sum := int32(0) for _, v := range visited { if v { sum++ } } ok = sum == m return } func NewHeap[H any](less func(a, b H) bool, nums []H) *Heap[H] { nums = append(nums[:0:0], nums...) heap := &Heap[H]{less: less, data: nums} heap.heapify() return heap } type Heap[H any] struct { data []H less func(a, b H) bool } func (h *Heap[H]) Push(value H) { h.data = append(h.data, value) h.pushUp(h.Len() - 1) } func (h *Heap[H]) Pop() (value H) { if h.Len() == 0 { panic("heap is empty") } value = h.data[0] h.data[0] = h.data[h.Len()-1] h.data = h.data[:h.Len()-1] h.pushDown(0) return } func (h *Heap[H]) Top() (value H) { value = h.data[0] return } func (h *Heap[H]) Len() int { return len(h.data) } func (h *Heap[H]) heapify() { n := h.Len() for i := (n >> 1) - 1; i > -1; i-- { h.pushDown(i) } } func (h *Heap[H]) pushUp(root int) { for parent := (root - 1) >> 1; parent >= 0 && h.less(h.data[root], h.data[parent]); parent = (root - 1) >> 1 { h.data[root], h.data[parent] = h.data[parent], h.data[root] root = parent } } func (h *Heap[H]) pushDown(root int) { n := h.Len() for left := (root<<1 + 1); left < n; left = (root<<1 + 1) { right := left + 1 minIndex := root if h.less(h.data[left], h.data[minIndex]) { minIndex = left } if right < n && h.less(h.data[right], h.data[minIndex]) { minIndex = right } if minIndex == root { return } h.data[root], h.data[minIndex] = h.data[minIndex], h.data[root] root = minIndex } }