8193번 - 킹세종 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 124 | 55 | 44 | 44.000% |
문제
세종이는 행성이 n개 있는 태양계의 왕이다. 행성 수가 너무 많아서 이름을 일일이 붙이는 것은 포기한 지 오래고, 대신 1~n의 구분되는 번호로 표기한다. 세종이의 집은 1번 행성에, PC방은 2번 행성에 위치한다. 또한 세종이는 고대부터 그 누구보다도 빠르게 PC방으로 달려가 핫타임을 놓치지 않기 위해 1번, 2번 행성을 왕래하게 해 주는 전용 비밀 양방향 텔레포터를 마련하고 있었으며, 한 번 이동하는 데 250분이 걸린다.
시대가 발전하여 각 행성들 사이에 교통을 위한 텔레포터가 많이 생겼다. 각각의 텔레포터는 양방향이고 이동에 정확히 한 시간이 걸린다. 행성의 시민들은 행성경제 활성화를 위하여 더 많은 텔레포터를 설치해줄 것을 세종이에게 부탁하였다.
세종이는 성군이 되기 위해 최대한 많은 부탁을 들어주려고 하지만, 단 한 가지는 용납할 수 없다. 텔레포터가 추가로 설치되다가 1번, 2번 행성 사이의 이동 시간이 자신의 비밀 텔레포터를 사용한 것, 즉 250분보다 빨라지는 것이다. 그러면 세종이가 핫타임 이벤트에 참가하기 위해 PC방 자리를 잡는 것에 차질이 생길지도 모른다.
따라서 세종이는 1번, 2번 행성을 교통 텔레포터들을 사용해 왕래하는 데 항상 250분보다 많은 시간이 들게 하면서 태양계에 최대한 많은 텔레포터를 설치하고 싶다. 몇 개의 텔레포터를 설치할 수 있을까? 물론 동일한 행성 쌍 사이에 여러 개의 텔레포터를 설치하는 건 무의미하기 때문에 그런 행동은 피할 것이다. 세종이가 그런 무의미한 곳에 비용을 들일 바에 차라리 자기 캐릭터에 현질을 하는 게 이득이다.
입력
첫째 줄에 행성 수 n과 이미 설치된 교통 텔레포터 수 m이 주어진다. (2 ≤ n ≤ 40,000, 0 ≤ m ≤ 1,000,000)
둘째 줄부터 m개의 줄에 걸쳐 기존의 각 텔레포터가 연결한 서로 다른 두 행성의 번호가 주어진다. 각 번호는 1 이상 n 이하의 정수이다. 여기엔 세종이의 전용 텔레포터는 포함되어 있지 않다. 같은 곳을 연결하는 텔레포터가 2번 이상 등장하지 않는다.
기존에 연결된 텔레포터만을 가지고는 어떠한 경로를 거치더라도 1번 행성과 2번 행성 사이를 250분 미만의 시간으로 왕래할 수 없음이 보장된다. 물론 그 이상이 시간으로 왕래가 가능할 수는 있다.
출력
첫째 줄에 추가로 건설할 수 있는 텔레포터 개수의 최댓값을 출력한다.
예제 입력 1
10 10 1 3 3 5 5 7 7 9 2 9 1 4 4 6 6 8 8 10 2 10
예제 출력 1
10
힌트
예제를 그림으로 나타낸 것이다. 실선이 이미 연결된 텔레포터이며 점선이 최대한 더 지을 수 있는 텔레포터들을 나타낸 것이다.
출처
Olympiad > Polish Olympiad in Informatics > POI 2009/2010 > Stage 2 5번
- 문제를 번역한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호