結果

問題 No.1640 簡単な色塗り
ユーザー 草苺奶昔草苺奶昔
提出日時 2024-09-13 02:55:18
言語 Go
(1.22.1)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 3,497 bytes
コンパイル時間 12,215 ms
コンパイル使用メモリ 222,936 KB
実行使用メモリ 16,264 KB
最終ジャッジ日時 2024-09-13 02:55:46
合計ジャッジ時間 26,595 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 141 ms
16,264 KB
testcase_05 AC 141 ms
16,168 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 109 ms
9,964 KB
testcase_11 AC 89 ms
10,016 KB
testcase_12 AC 75 ms
7,968 KB
testcase_13 AC 182 ms
14,144 KB
testcase_14 AC 175 ms
14,100 KB
testcase_15 AC 53 ms
7,840 KB
testcase_16 AC 70 ms
7,828 KB
testcase_17 AC 147 ms
12,056 KB
testcase_18 AC 11 ms
6,944 KB
testcase_19 AC 79 ms
7,952 KB
testcase_20 AC 105 ms
9,960 KB
testcase_21 AC 85 ms
10,016 KB
testcase_22 AC 8 ms
6,940 KB
testcase_23 AC 113 ms
9,956 KB
testcase_24 AC 30 ms
6,940 KB
testcase_25 AC 78 ms
7,960 KB
testcase_26 AC 133 ms
12,052 KB
testcase_27 AC 52 ms
7,572 KB
testcase_28 AC 163 ms
14,160 KB
testcase_29 AC 131 ms
9,964 KB
testcase_30 AC 21 ms
6,940 KB
testcase_31 AC 154 ms
14,080 KB
testcase_32 AC 130 ms
12,104 KB
testcase_33 AC 90 ms
9,928 KB
testcase_34 AC 116 ms
12,032 KB
testcase_35 AC 89 ms
9,924 KB
testcase_36 AC 21 ms
6,940 KB
testcase_37 AC 29 ms
6,940 KB
testcase_38 AC 139 ms
14,132 KB
testcase_39 AC 58 ms
7,744 KB
testcase_40 AC 57 ms
7,824 KB
testcase_41 AC 118 ms
12,028 KB
testcase_42 AC 68 ms
9,992 KB
testcase_43 AC 67 ms
9,992 KB
testcase_44 AC 68 ms
9,992 KB
testcase_45 AC 52 ms
7,624 KB
testcase_46 AC 24 ms
6,940 KB
testcase_47 AC 15 ms
6,944 KB
testcase_48 AC 144 ms
14,104 KB
testcase_49 AC 6 ms
6,944 KB
testcase_50 AC 1 ms
6,940 KB
testcase_51 AC 1 ms
6,940 KB
testcase_52 AC 173 ms
16,244 KB
testcase_53 AC 173 ms
16,208 KB
07_evil_01.txt AC 428 ms
24,644 KB
07_evil_02.txt AC 703 ms
37,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
	}
}
0