邏輯電路 (APCS 2024-01 中高級)

請設計一個程式，模擬一個基本的邏輯電路系統。這個電路由輸入端口、邏輯閘及輸出端口組成。你需要模擬訊號傳遞與邏輯閘運算，求出所有輸出端口的數值，並計算電路的最大延遲時間。

電路包含下列元件：

• 輸入端口：共有 \(p\) 個，編號為 \(1\) 到 \(p\)。每個輸入值為 \(0\) 或 \(1\)。
• 邏輯閘：共有 \(q\) 個，編號為 \(p+1\) 到 \(p+q\)。閘的類型如下：
  • 類型 \(1\)，AND：兩個輸入都是 \(1\) 時輸出 \(1\)，否則輸出 \(0\)。
  • 類型 \(2\)，OR：至少一個輸入是 \(1\) 時輸出 \(1\)，否則輸出 \(0\)。
  • 類型 \(3\)，XOR：兩個輸入不同時輸出 \(1\)，否則輸出 \(0\)。
  • 類型 \(4\)，NOT：只有一個輸入，輸出為該輸入的反值。
• 輸出端口：共有 \(r\) 個，編號為 \(p+q+1\) 到 \(p+q+r\)。每個輸出端口接收一個訊號。

電路中的每條連接線都有方向。最大延遲時間是：在所有從輸入端口到輸出端口的路徑中，路徑經過的邏輯閘數量最大值。輸入端口與輸出端口本身不計入。

輸入格式

第一行包含四個整數 \(p,q,r,m\)，依序代表輸入端口、邏輯閘、輸出端口及連接線的數量。

第二行包含 \(p\) 個整數 \(v_1,v_2,\ldots,v_p\)，依序為各輸入端口的值。

第三行包含 \(q\) 個整數 \(t_1,t_2,\ldots,t_q\)，其中 \(t_i\) 是編號 \(p+i\) 的邏輯閘類型。

接下來 \(m\) 行，每行包含兩個整數 \(a,b\)，表示一條從元件 \(a\) 指向元件 \(b\) 的連接線。

限制

• \(1\le p\le 10^3\)
• \(1\le q\le 5\times 10^4\)
• \(1\le r\le 10^3\)
• 每個 AND、OR、XOR 閘恰有兩條輸入線；每個 NOT 閘恰有一條輸入線。
• 每個輸出端口恰有一條輸入線。
• 每個輸入端口及每個邏輯閘的輸出，會連到至少 \(1\) 個、至多 \(20\) 個其他邏輯閘或輸出端口。
• 電路不會形成迴路。
• 測試資料保證最大延遲時間不超過 \(100\)。

輸出格式

第一行輸出一個整數，表示電路的最大延遲時間。

第二行依編號由小到大輸出 \(r\) 個以空白分隔的整數，表示各輸出端口的值。

評分說明

本題共有 \(20\) 筆計分測試資料，每筆 \(5\) 分。

範例輸入 1

4 5 4 13
1 0 1 0
1 2 3 4 1
1 5
2 5
2 6
3 6
3 7
4 7
4 8
5 10
6 9
6 11
7 9
8 13
9 12

範例輸出 1

2
0 1 1 1

範例輸入 2

5 6 4 15
1 1 0 1 0
2 1 3 4 1 3
1 6
2 7
7 13
7 6
3 7
3 8
4 8
5 9
8 10
9 10
10 14
10 11
9 11
6 12
11 15

範例輸出 2

3
1 0 1 0

題目來源

APCS 2024 年 1 月實作題第 3 題，ZeroJudge m933 邏輯電路。