結果

問題 No.1293 2種類の道路
ユーザー 草苺奶昔
提出日時 2023-03-12 10:41:42
言語 Go
(1.23.4)
結果
AC  
実行時間 515 ms / 2,000 ms
コード長 3,373 bytes
コンパイル時間 11,145 ms
コンパイル使用メモリ 235,888 KB
実行使用メモリ 92,032 KB
最終ジャッジ日時 2024-09-18 06:58:00
合計ジャッジ時間 17,898 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"bufio"
"fmt"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, road1, road2 int
fmt.Fscan(in, &n, &road1, &road2)
scc := NewStronglyConnectedComponents(2 * n)
for i := 0; i < road1; i++ {
var a, b int
fmt.Fscan(in, &a, &b)
a, b = a-1, b-1
scc.AddEdge(2*a, 2*b, 1)
scc.AddEdge(2*b, 2*a, 1)
}
for i := 0; i < road2; i++ {
var a, b int
fmt.Fscan(in, &a, &b)
a, b = a-1, b-1
scc.AddEdge(2*a+1, 2*b+1, 1)
scc.AddEdge(2*b+1, 2*a+1, 1)
}
for i := 0; i < n; i++ {
scc.AddEdge(2*i, 2*i+1, 1)
}
scc.Build()
v := len(scc.Group)
dp := make([]int, v)
for i := 0; i < n; i++ {
dp[scc.CompId[2*i]]++
}
for i := 0; i < v; i++ {
for _, e := range scc.Dag[i] {
dp[e.to] += dp[e.from]
}
}
res := 0
for i := 0; i < n; i++ {
res += dp[scc.CompId[2*i+1]] - 1 // !1
}
fmt.Fprintln(out, res)
}
type WeightedEdge struct{ from, to, cost, index int }
type StronglyConnectedComponents struct {
G [][]WeightedEdge //
Dag [][]WeightedEdge // DAG
CompId []int //
Group [][]int //
rg [][]WeightedEdge
order []int
used []bool
eid int
}
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, scc.eid})
scc.eid++
}
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, e.index})
}
}
scc.CompId = make([]int, len(scc.G))
for i := range scc.CompId {
scc.CompId[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.CompId[v] == -1 {
scc.rdfs(v, ptr)
ptr++
}
}
dag := make([][]WeightedEdge, ptr)
visited := make(map[int]struct{}) //
for i := range scc.G {
for _, e := range scc.G[i] {
x, y := scc.CompId[e.from], scc.CompId[e.to]
if x == y {
continue
}
hash := x*len(scc.G) + y
if _, ok := visited[hash]; !ok {
dag[x] = append(dag[x], WeightedEdge{x, y, e.cost, e.index})
visited[hash] = struct{}{}
}
}
}
scc.Dag = dag
scc.Group = make([][]int, ptr)
for i := range scc.G {
scc.Group[scc.CompId[i]] = append(scc.Group[scc.CompId[i]], i)
}
}
// k
func (scc *StronglyConnectedComponents) Get(k int) int {
return scc.CompId[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.CompId[idx] != -1 {
return
}
scc.CompId[idx] = cnt
for _, e := range scc.rg[idx] {
scc.rdfs(e.to, cnt)
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0