10287번 - Spy Network 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 48 | 23 | 19 | 44.186% |
문제
NSA가 아주 짱짱 큰 정수를 소인수분해하는 알고리즘을 발견했다! 그들은 조직 내의 spy network에서 암호화된 메시지를 주고받는 데 이 알고리즘을 적극 활용하기로 하였다. 그들의 spy network는 방향 그래프 G = (V, E)의 형태로 표현될 수 있으며, 각 정점은 NSA의 직원을 의미하고 각 간선 (u, v)는 u가 v에게 비밀스럽게 정보를 보낼 수 있음을 의미하며, 이는 v가 u의 연락망에 속해 있다고도 표현할 수 있다. u가 v에게 정보를 보낼 수 있다고 해서 v가 u에게 정보를 보낼 수 있지는 않다는 것에 주의하라.
NSA의 직원들은 항상 알려진 테러 조직들의 테러 조짐을 관찰하고 있으며 몇 달의 기한마다 동료들에게 어떤 테러 조직이 테러를 일으킬 조짐이 보이는지를 보고한다.
정보 전달 방식은 이렇다.
- 모든 직원들은 자신이 모은 정보를 자신의 연락망에 속한 다른 직원들에게 보낸다.
- 만약 어떤 직원이 정보 ireceived를 받았다면, 자신이 지금까지 가지고 있던 정보 iold와 결합하여 새로운 정보 inew를 생성하고, 그것을 자신의 최신 정보로 대체한다.
- 이때, inew는 ireceived와 iold에 모두 포함되어 있던 정보만으로 생성된다. 이는 워낙에 NSA에 거짓 정보가 많이 흘러들어오기에, 여러 직원이 발견하지 못했다면 진실이라는 당위성이 떨어진다고 판단하기로 했기 때문이다.
- 그 다음부터 해당 직원이 다른 직원에게 보낼 정보는 inew이다.
모든 직원들은 정보를 전달할 때 이런 과정을 따른다.
만약 직원들이 정보를 계속해서 주고받으면, 어느 순간부터 아무리 정보를 보내도 그 어떤 정보도 갱신되지 않는 일이 발생한다. 이때 모든 직원들은 정보 송신을 그만둔다. Spy network 전체가 연결되어 있지 않을 수도 있고, 싸이클이 존재할 수도 있음에 유의하라.
NSA는 이러한 정보의 형태를 큰 소수의 곱으로 나타내기로 했다. 모든 테러 조직마다 대응하는 큰 소수값을 부여한 후(다른 조직은 다른 값을 부여받는다), 여러 조직을 표현하는 정보는 그 소수들의 곱으로 나타낸다. 만약 어떤 사원이 ireceived를 받았다면, inew는 ireceived와 iold의 최대공약수(greatest common divisor)가 될 것이다. 왜냐하면 두 정보의 최대공약수가 두 정보에 모두 포함되어 있는 소수들만의 곱이기 때문이다. 이렇게 정보를 전달하다가 정보 송신이 중단된 경우, 어떤 직원은 중요한 상황에 소인수분해 알고리즘을 사용하여 조직의 정보를 파악할 수 있다.
NSA는 최근에 자신들의 정보가 외부로 유출되었음을 확인했다! 모든 정보는 암호화되어 있고 잃어버린 정보 또한 없지만, NSA는 정보 유출자를 찾아내기로 결정했다. 이에 당신의 도움이 필요하다. 정확히 누가 정보를 유출했는지는 알 수 없지만, NSA는 유출된 정보의 값을 알고 있었다. 만약 spy network가 더 이상의 어떠한 정보 갱신도 이루어지지 않는 상태가 되었을 때, 유출된 정보의 값을 가지고 있던 직원들이 누구인지를 아는 것부터 시작하기로 했다. 그렇게 한다면 수색망을 좁힐 수 있기 때문이다.
최종 상태에서 누출된 정보값을 가지고 있는 직원의 수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 첫 번째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.
각 테스트 케이스의 첫 번째 줄에는 세 정수 N, M, L이 주어진다. (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 10 000, 1 ≤ l < 263) N은 직원의 수, M은 간선의 수, L은 누출된 정보값을 의미한다.
이어지는 M개의 줄에 간선의 정보가 하나씩 주어진다. 한 줄에 두 정수 a, b가 주어지는데, 이는 b가 a의 연락망에 속해 있음을 의미한다. (1 ≤ a, b ≤ n, a ≠ b)
이어지는 N개의 줄에 각 직원이 처음에 가지고 있던 정보값 i가 주어진다. (1 ≤ i < 263)
출력
각 테스트 케이스마다 한 줄에 걸쳐서 최종 상태에서 누출된 정보값을 가지고 있던 직원의 수를 출력한다.
예제 입력 1
3 4 3 7 1 3 2 3 3 4 35 77 385 385 4 4 159 1 2 2 3 3 1 4 1 159 159 159 2014 5 5 9 2 1 2 3 3 2 3 4 5 4 27 54 90 315 135
예제 출력 1
2 0 2
힌트
첫 번째 테스트 케이스의 spy network이다.
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2014 Preliminaries G번
- 문제를 번역한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호