R00387
위원회 구성
플래티넘 IV레이팅
의견: 0
설명
\(N\)명의 후보가 있다. 각 후보를 위원회에 포함하거나 제외해야 한다. \(M\)개의 제약이 종류 번호 \(t\)와 두 후보 \(a, b\)로 주어진다.
- \(t=1\) : \(a\)와 \(b\) 중 적어도 한 명은 포함되어야 한다.
- \(t=2\) : \(a\)와 \(b\)가 동시에 포함될 수는 없다.
- \(t=3\) : \(a\)와 \(b\) 중 적어도 한 명은 제외되어야 한다.
- \(t=4\) : \(a\)와 \(b\) 중 정확히 한 명만 포함되어야 한다.
모든 제약을 만족하는 포함/제외 배정이 존재하면 가능, 없으면 불가능을 출력한다. (배정 자체는 출력하지 않는다.)
제약
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le t \le 4\), \(1 \le a, b \le N\)
입력 형식
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 t a b (\(1 \le t \le 4\), \(1 \le a, b \le N\)).
출력 형식
가능 또는 불가능을 출력한다.
예제 1
입력
3 2
1 1 2
2 2 3
출력
가능설명
후보 3명. (1 또는 2 포함) and (2,3 동시 포함 금지). 예: 1만 포함하면 두 조건 모두 만족 → 가능.
예제 2
입력
2 3
1 1 2
2 1 2
4 1 2
출력
가능설명
후보 2명. (1또는2 포함), (1,2 동시포함 금지), (정확히 한 명만). 1만 포함하거나 2만 포함하면 모두 만족 → 가능.
다이아몬드 III문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
위원회 구성
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
위원회 구성
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기