917 . 你要不要參加 IOIC

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

蔡兆豐
大家好，我是蔡兆豐。我們今天要介紹的書是我兒佳比。這本書是在講述一個名叫科。克萊爾的傳奇故事。他本來居住在童話社區，每個人都被要求。要一樣。

User's AC Ratio

85.0% (17/20)

Submission's AC Ratio

55.1% (27/49)

Tags

ioicamp ioicamp-2025

Description

2024 年 12 月 5 號，小七和小八上了一整天的課，好不容易撐到了放學。傍晚，他們一起去吃晚餐。

小七嘆了口氣，因為上課上了好幾天，已經三天沒有練習程式競賽，他覺得自己面目可憎。他說：「明天就要出發去參加全國賽了，好緊張。」

「真羨慕你，可以去參加全國賽。」小八在區賽失手，與全國賽的參賽名額失之交臂。

「那你要不要參加 IOICamp？報名三天後就截止了。」小七直接鬼轉話題。

「你去的話我一定去。」

「我當然會去啊。」小七說。

這個時候，剛好也在這間餐廳吃飯的小魚跑過來說：「欸欸小八，你要去 IOIC？你去的話我一定去。」

接下來，他們幾人熱烈地討論有誰會去 IOIC。

聞言，老闆也跑來：「你們要去參加 IOIC？我兒子說如果小八去了，那他一定會去，喔不過他不喜歡隔壁班的小波，要是小波去了，我兒子一定不會去。」

小七看見這麼多人在他的大力推薦之下，對參加 IOIC 有興趣，他感到很開心，但他也想到了一個問題：如果小八跟小波都去了 IOIC，那老闆的兒子到底是會還是不會去 IOIC 呢？要是要讓每個人說出的條件都被滿足，那麼唯一一種可能發生的狀況就是小七、小八、小魚、老闆兒子都去了 IOIC，而小波沒有去。

小七對這個問題很感興趣，剛好最近有很多人在討論要不要參加 IOIC，於是他收集了一些情報，有 $N$ 個他想知道會不會去 IOIC 的人，以 $1,2,\dots,N$ 編號，他得知了 $M$ 條消息，消息有 2 種：

  • $1\ i\ x$（$1 \leq i \leq N$、$x \in \lbrace 0,1\rbrace$）：$x=1$ 代表第 $i$ 個人說「我一定會去 IOIC」，$x=0$ 則代表他說「我一定不會去 IOIC」。
  • $2\ i\ j\ x\ y$（$1 \leq i,j \leq N$、$x,y \in \lbrace 0,1\rbrace$、$i \neq j$）：第 $j$ 個人說，要是第 $i$ 個人會（$x=1$）/ 不會（$x=0$）去 IOIC，那我一定會（$y=1$）/ 不會（$y=0$）去。舉例來說，$x=1、y=0$ 代表第 $j$ 個人說如果第 $i$ 個人去 IOIC，他就不去。

小七想知道，如果每個人的選擇都只有去跟不去這兩種可能，那存不存在一種狀況滿足所有情報給出的條件，如果有的話，他還想知道一種滿足所有條件的情況。

注意條件反過來不一定要成立，例如「小波去了的話老闆兒子就不會去」這個條件只要求要是小波選擇去 IOIC，老闆兒子就不會去，而不要求老闆兒子不去，小波就會去。

Input Format

第一行有一個整數 $T$，代表測試資料的數量。

每筆測試資料的第一行有兩個整數 $N,M$，分別代表小七想知道會不會去 IOIC 的人數，以及小七知道的消息數量。

接下來有 $M$ 行，每一行代表一條消息。一條消息的格式是 $1\ i\ x$ 或 $2\ i\ j\ x\ y$，意義如題目敘述所述。

  • $1 \leq T \leq 3 \times 10^ 5$
  • $2 \leq N \leq 3 \times 10^ 5$
  • $0 \leq M \leq 3 \times 10^ 5$
  • $1 \leq i,j \leq n$
  • $x,y \in \lbrace 0,1\rbrace$
  • 對於第 2 種消息，$i \neq j$
  • $\sum N, \sum M \leq 3 \times 10^ 5$

Output Format

對於每筆測試資料，第一行輸出 YES 或 NO，代表是否存在一種狀況滿足所有消息中描述的條件。

如果第一行輸出的結果是 YES，第二行輸出 $N$ 個整數 $z_1,z_2,\dots,z_N$，表示一種滿足所有條件的狀況，其中 $z_i=1$ 代表第 $i$ 個人選擇去 IOIC、$z_i=0$ 則代表他選擇不去。若有多種解，輸出任意一個即可。

如果你第一行的輸出正確，但是在答案為 YES 時構造的狀況不滿足所有條件，那麼你可以得到 $30\%$ 的分數。注意答案為 NO 時請不要輸出第二行，且答案為 YES 時還是要按照格式要求輸出第二行。

Sample Input 1

3
5 5
2 1 2 1 1
1 1 1
2 2 3 1 1
2 2 4 1 1
2 5 4 1 0
2 2
2 1 2 1 0
2 2 1 0 0
2 3
2 1 2 1 0
2 2 1 0 0
1 1 1

Sample Output 1

YES
1 1 1 1 0
YES
0 0
NO

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
Submit
Back to Top