2416번 - 문 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 386 | 82 | 58 | 23.673% |
문제
수십년간 소프트웨어 엔지니어로 일해온 백승환은 이제 전혀 다른 일을 시작하기로 했다. 승환이는 여러 가지 일자리를 살펴보고 있었고, 승환이의 눈을 사로잡은 직업이 하나 있었으니… 그것은 양식업이었다.
오늘은 승환이가 출근한 첫 날이다.
승환이의 상사 규현이는 이미 승환이가 할 일을 정해놓았다. 승환이는 저수지 하나를 다른 것들로 부터 격리시켜야 한다.다음은 승환이가 생각한 방법이다.
두 저수지는 여러개의 수로로 서로 연결되어 있다. 각 수로에는 두 개의 문이 있다. 두 문이 모두 열려있으면, 수로는 열려있는 것이고, 그렇지 않으면 닫혀있는 것이다. 문은 스위치로 작동한다 하나의 스위치는 여러개의 문을 작동시킬 수 있지만, 각각의 문은 오직 단 하나의 스위치로만 작동시킬 수 있다. 하나의 스위치로 어떤 수로의 두 문을 작동 시키는 것이나, 스위치가 작동시킬 수 있는 문이 없는 것도 가능하다
위의 그림은 3개의 수로와 2개의 스위치가 있는 예이다.
스위치는 다음 두 가지 방법 중의 한 방법으로 문을 작동 시킨다.
- 스위치가 켜져있으면, 문이 열려있고, 스위치가 꺼져있으면, 문이 닫혀있다.
- 스위치가 켜져있으면, 문이 닫혀있고, 스위치가 꺼져있으면, 문이 열려있다.
승환이는 스위치를 가지고 조금 놀다가, 지금까지 수십년간 일해온 프로그래밍 스킬을 여기에 적용시킬 수 있다는 사실을 알았다. 문과 스위치간의 연결 설정이 주어졌을 때, 모든 수로를 닫는 것이 가능한지 구하는 프로그램을 작성하시오. 만약, 가능하다면, 각 스위치가 켜져야하는지, 꺼져야하는지, 상태를 출력한다.
입력
첫째 줄에 수로의 개수 N (1 ≤ N ≤ 250,000)과 스위치의 개수 M (1 ≤ M ≤ 500,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 수로의 정보가 주어진다. 수로의 정보는 4개의 숫자로 이루어져 있고, a, sa, b, sb라고 한다. a와 b (1 ≤ a, b ≤ m)은 연결되어 문을 작동시키는 스위치이다. sa와 sb는 0과 1 중의 하나이다. si가 0이면, 스위치 i가 꺼져야 문이 닫히는 것이고, si가 1이면, 스위치 i가 켜져야 문이 닫히는 것이다.
출력
모든 수로를 닫는 것이 가능하면, m개의 줄에, 각 스위치가 꺼져야 하면 0을, 켜져야 하면 1을 출력한다. 여러 가지가 있으면, 아무거나 출력해도 된다.
모든 수로를 닫는 것이 불가능하다면, IMPOSSIBLE을 출력한다.
예제 입력 1
3 2 1 0 2 1 1 0 2 0 1 1 2 1
예제 출력 1
0 1
예제 입력 2
2 1 1 0 1 0 1 1 1 1
예제 출력 2
IMPOSSIBLE
출처
Olympiad > Baltic Olympiad in Informatics > BOI 2008 2번
- 문제를 번역한 사람: baekjoon
- 문제의 오타를 찾은 사람: leejseo
- 잘못된 데이터를 찾은 사람: WeissBlume
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호