768 . 派對分組

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

50.0% (2/4)

Tags

apcsc apcsc-graph

Description

作為一個派對負責人，你想要舉辦兩場派對並邀請 $N$ 個朋友到其中一場。每個朋友都對派對有所期待，他們一共提出 $L$ 個派對應具備的特質，例如派對蛋糕上有沒有香菜。這些特質有些人贊成，也有些人反對，也有些人沒意見。你可以自由規劃派對，然而當有兩個人對某個特質意見互相衝突時 (一人贊成一人反對)，勢必會有一人感到不開心。想請問你是否能適當安排 $N$ 個朋友到兩場派對的其中一場，使得同一場派對沒有兩個人有衝突意見？

Input Format

本題含多筆測試資料，第一行代表測試資料筆數 $T$。
每筆測試資料第一行是兩個空白分隔的正整數 $N, L$，分別代表朋友人數和派對特質數。
接著有 $N$ 行每行有若干個空白分隔的整數，並恰有兩個 $0$，其中第二個 $0$ 一定在結尾。
在第 $i$ 行第一個 $0$ 以前的正整數代表朋友 $i$ 贊成的特質，第一個 $0$ 以後第二個 $0$ 以前的正整數是朋友 $i$ 反對的特質。

輸入保證 $T\le 100$，$N\le 1000$，$L \leq 10^ 6$，派對特質編號 $1\sim L$。假設 $S$ 是總意見數，那麼保證 $S\le 10^ 5$。

Output Format

對於每筆測試資料輸出一行，如果可以適當安排請輸出 Yes，否則輸出 No。

Sample Input 1

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

Sample Output 1

Yes
No

Hints

Problem Source

TIOJ 1192 鑰匙設計

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
Submit
Back to Top