結果

問題 No.274 The Wall
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-21 10:51:38
言語 Go
(1.22.1)
結果
MLE  
実行時間 -
コード長 4,860 bytes
コンパイル時間 14,351 ms
コンパイル使用メモリ 218,128 KB
実行使用メモリ 767,912 KB
最終ジャッジ日時 2023-09-29 04:51:32
合計ジャッジ時間 20,808 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1,969 ms
417,360 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 MLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	const INF int = int(1e18)
	const MOD int = 998244353

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)
	color := make([][]int, n) // [left,right]
	for i := 0; i < n; i++ {
		var l, r int
		fmt.Fscan(in, &l, &r)
		color[i] = []int{l, r}
	}

	isOverlapped := func(left1, right1, left2, right2 int) bool {
		start := max(left1, left2)
		end := min(right1, right2)
		return start <= end
	}

	// n个命题分别为[第i个砖块不旋转]
	// 每两个之间验证四种情况
	ts := NewTwoSat(n)
	for i := 0; i < n; i++ {
		left1, right1 := color[i][0], color[i][1]
		revLeft1, revRight1 := m-1-right1, m-1-left1
		for j := i + 1; j < n; j++ {
			left2, right2 := color[j][0], color[j][1]
			revLeft2, revRight2 := m-1-right2, m-1-left2
			// 1. 两个砖块都不旋转
			if isOverlapped(left1, right1, left2, right2) {
				ts.AddNand(i, j)
			}

			// 2. 第一个砖块旋转,第二个砖块不旋转
			if isOverlapped(revLeft1, revRight1, left2, right2) {
				ts.AddNand(ts.Rev(i), j)
			}

			// 3. 第一个砖块不旋转,第二个砖块旋转
			if isOverlapped(left1, right1, revLeft2, revRight2) {
				ts.AddNand(i, ts.Rev(j))
			}

			// 4. 两个砖块都旋转
			if isOverlapped(revLeft1, revRight1, revLeft2, revRight2) {
				ts.AddNand(ts.Rev(i), ts.Rev(j))
			}
		}
	}

	_, ok := ts.Solve()
	if !ok {
		fmt.Fprintln(out, "NO")
		return
	}

	fmt.Fprintln(out, "YES")

}

type TwoSat struct {
	sz  int
	scc *StronglyConnectedComponents
}

func NewTwoSat(n int) *TwoSat {
	return &TwoSat{sz: n, scc: NewStronglyConnectedComponents(n + n)}
}

// u -> v <=> !v -> !u
func (ts *TwoSat) AddIf(u, v int) {
	ts.scc.AddEdge(u, v, 1)
	ts.scc.AddEdge(ts.Rev(v), ts.Rev(u), 1)
}

// u or v <=> !u -> v
func (ts *TwoSat) AddOr(u, v int) {
	ts.AddIf(ts.Rev(u), v)
}

// u nand v <=> u -> !v
func (ts *TwoSat) AddNand(u, v int) {
	ts.AddIf(u, ts.Rev(v))
}

// u <=> !u -> u
func (ts *TwoSat) SetTrue(u int) {
	ts.scc.AddEdge(ts.Rev(u), u, 1)
}

// !u <=> u -> !u
func (ts *TwoSat) SetFalse(u int) {
	ts.scc.AddEdge(u, ts.Rev(u), 1)
}

func (ts *TwoSat) Rev(u int) int {
	if u >= ts.sz {
		return u - ts.sz
	}
	return u + ts.sz
}

func (ts *TwoSat) Solve() (res []bool, ok bool) {
	ts.scc.Build()
	res = make([]bool, ts.sz)
	for i := 0; i < ts.sz; i++ {
		if ts.scc.Comp[i] == ts.scc.Comp[ts.Rev(i)] {
			return
		}
		res[i] = ts.scc.Comp[i] > ts.scc.Comp[ts.Rev(i)]
	}
	ok = true
	return
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type WeightedEdge struct{ from, to, cost int }
type StronglyConnectedComponents struct {
	G     [][]*WeightedEdge // 原图
	Dag   [][]*WeightedEdge // 强连通分量缩点后的顶点和边组成的DAG
	Comp  []int             //每个顶点所属的强连通分量的编号
	Group [][]int           // 每个强连通分量所包含的顶点
	rg    [][]*WeightedEdge
	order []int
	used  []bool
}

func NewStronglyConnectedComponents(n int) *StronglyConnectedComponents {
	return &StronglyConnectedComponents{G: make([][]*WeightedEdge, n)}
}

func (scc *StronglyConnectedComponents) AddEdge(from, to, cost int) {
	scc.G[from] = append(scc.G[from], &WeightedEdge{from, to, cost})
}

func (scc *StronglyConnectedComponents) Build() {
	scc.rg = make([][]*WeightedEdge, len(scc.G))
	for i := range scc.G {
		for _, e := range scc.G[i] {
			scc.rg[e.to] = append(scc.rg[e.to], &WeightedEdge{e.to, e.from, e.cost})
		}
	}

	scc.Comp = make([]int, len(scc.G))
	for i := range scc.Comp {
		scc.Comp[i] = -1
	}
	scc.used = make([]bool, len(scc.G))
	for i := range scc.G {
		scc.dfs(i)
	}
	for i, j := 0, len(scc.order)-1; i < j; i, j = i+1, j-1 {
		scc.order[i], scc.order[j] = scc.order[j], scc.order[i]
	}

	ptr := 0
	for _, v := range scc.order {
		if scc.Comp[v] == -1 {
			scc.rdfs(v, ptr)
			ptr++
		}
	}

	dag := make([][]*WeightedEdge, ptr)
	for i := range scc.G {
		for _, e := range scc.G[i] {
			x, y := scc.Comp[e.from], scc.Comp[e.to]
			if x == y {
				continue
			}
			dag[x] = append(dag[x], &WeightedEdge{x, y, e.cost})
		}
	}
	scc.Dag = dag

	scc.Group = make([][]int, ptr)
	for i := range scc.G {
		scc.Group[scc.Comp[i]] = append(scc.Group[scc.Comp[i]], i)
	}
}

// 获取顶点k所属的强连通分量的编号
func (scc *StronglyConnectedComponents) Get(k int) int {
	return scc.Comp[k]
}

func (scc *StronglyConnectedComponents) dfs(idx int) {
	tmp := scc.used[idx]
	scc.used[idx] = true
	if tmp {
		return
	}
	for _, e := range scc.G[idx] {
		scc.dfs(e.to)
	}
	scc.order = append(scc.order, idx)
}

func (scc *StronglyConnectedComponents) rdfs(idx int, cnt int) {
	if scc.Comp[idx] != -1 {
		return
	}
	scc.Comp[idx] = cnt
	for _, e := range scc.rg[idx] {
		scc.rdfs(e.to, cnt)
	}
}
0