작업 시간대 배정
플래티넘 IV의견: 0
\(N\)개의 작업을 각각 오전(0) 또는 오후(1)에 배정한다. \(M\)개의 제약이 a va b vb로 주어지며, 이는 "작업 \(a\)를 시간대 \(va\)에 두거나, 작업 \(b\)를 시간대 \(vb\)에 두어야 한다"는 절(clause)을 의미한다.
모든 제약을 동시에 만족하는 배정이 존재하면 가능, 없으면 불가능을 출력한다.
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le a, b \le N\), \(va, vb \in \{0,1\}\)
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 a va b vb (\(1 \le a, b \le N\), \(va, vb \in \{0,1\}\)).
가능 또는 불가능을 출력한다.
3 2
1 1 2 0
2 1 3 1
가능작업 3개. (1=오전 또는 2=오후), (1=오후 또는 3=오전). 1=오전,3=오전이면 둘째 절은 3=오전으로 만족, 첫 절은 1=오전으로 만족 → 가능.
2 4
1 1 2 1
1 0 2 0
1 1 2 0
1 0 2 1
불가능작업 2개. 네 절이 (1오전∨2오후),(1오후∨2오전),(1오전∨2오전),(1오후∨2오후). 어떤 배정도 한 절을 위반 → 불가능.
riseoj 작성
출처 Original
평가 및 의견
작업 시간대 배정
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
작업 시간대 배정