레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Regions
English 1.2
지역 (REGIONS)
국제 연합 지역 개발 기구(UNRDA)는 매우 잘 정의된 조직 구조를 가지고 있다. 이 기구는 총 N명을 고용하고 있으며, 각 직원은 세계의 지리적으로 구분되는 R개의 지역 중 한 곳 출신이다. 직원들에게는 연공서열 순으로 1부터 N까지 번호가 매겨져 있으며, 1번 직원인 의장이 가장 높다. 지역에는 특별한 순서 없이 1부터 R까지 번호가 매겨져 있다. 의장을 제외한 모든 직원에게는 상사가 정확히 한 명 있다. 상사는 항상 자신이 감독하는 직원보다 서열이 높다.
직원 A가 직원 B의 관리자라는 것은 A가 B의 상사이거나 A가 B의 상사의 관리자일 때, 그리고 그때뿐이다. 따라서 예를 들어 의장은 다른 모든 직원의 관리자이다. 또한 분명히 두 직원이 서로의 관리자일 수는 없다.
안타깝게도 국제 연합 조사국(UNBI)은 최근 UNRDA가 세계의 일부 지역을 다른 지역보다 우대하는 불균형한 조직 구조를 가지고 있다는 다수의 민원을 받았다. 이 혐의를 조사하기 위해 UNBI는 UNRDA의 감독 구조를 입력받아 다음 형태의 질의에 답할 수 있는 컴퓨터 시스템을 만들고자 한다: 서로 다른 두 지역 r1과 r2가 주어졌을 때, 직원 e1이 지역 r1 출신이고 직원 e2가 지역 r2 출신이며 e1이 e2의 관리자인 직원 쌍 e1, e2가 기구에 몇 쌍 있는가. 각 질의에는 두 매개변수, 즉 지역 r1과 r2가 있으며, 그 결과는 위 조건을 만족하는 서로 다른 쌍 e1, e2의 수인 정수 하나이다.
TASK
기구의 모든 직원의 출신 지역과 누가 누구에게 감독받는지에 대한 데이터가 주어졌을 때, 위에 설명한 질의에 대화식으로 답하는 프로그램을 작성하시오.
EXAMPLE
Sample Input
Sample Output
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
1 [flush standard output]
3 [flush standard output]
2 [flush standard output]
1 [flush standard output]
TESTING
대회 시스템의 테스트 인터페이스를 통해 풀이를 테스트하고 싶다면, 위의 예시 입력에서 보인 것처럼 입력 데이터와 모든 질의를 함께 포함한 입력 파일을 제공해야 한다.
\(1 \le N \le 200,000\)
직원의 수
\(1 \le R \le 25,000\)
지역의 수
\(1 \le Q \le 200,000\)
프로그램이 답해야 하는 질의의 수
\(1 \le Hk \le R\)
직원 k의 출신 지역 (1 ≤ k ≤ N에 대해)
\(1 \le Sk < k\)
직원 k의 상사 (2 ≤ k ≤ N에 대해)
\(1 \le r1, r2 \le R\)
질의에서 묻는 지역들
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N, R, Q가 이 순서로 공백 하나씩으로 구분되어 주어진다.
• 다음 N개의 줄에는 기구의 N명의 직원이 연공서열 순으로 주어진다. 이 N개의 줄 중 k번째 줄은 k번 직원을 나타낸다. 이 중 첫 줄(즉, 의장을 나타내는 줄)에는 의장의 출신 지역 H1인 정수 하나가 있다. 나머지 N-1개의 각 줄에는 공백 하나로 구분된 두 정수, 즉 직원 k의 상사 Sk와 직원 k의 출신 지역 Hk가 있다.
August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Regions
English 1.2
INTERACTION
입력 데이터를 읽은 뒤, 프로그램은 표준 입력에서 질의를 읽고 표준 출력에 질의 결과를 쓰는 것을 번갈아 시작해야 한다. Q개의 질의는 한 번에 하나씩 답해야 한다. 즉, 이미 받은 질의에 대한 응답을 보낸 뒤에야 다음 질의를 받을 수 있다.
각 질의는 표준 입력의 한 줄로 주어지며, 공백 하나로 구분된 서로 다른 두 정수, 즉 두 지역 r1과 r2로 이루어진다.
각 질의에 대한 응답은 표준 출력의 한 줄로, 정수 하나를 담아야 한다: e1의 출신 지역이 r1이고 e2의 출신 지역이 r2이며 e1이 e2의 관리자인 UNRDA 직원 쌍 e1, e2의 수.
NOTE: 테스트 데이터는 표준 입력으로 주어지는 어떤 질의에 대해서도 올바른 답이 항상 1,000,000,000 미만이 되도록 만들어져 있다.
IMPORTANT NOTE: 그레이더와 올바르게 상호작용하려면, 프로그램은 매 질의 응답 후에 표준 출력을 플러시해야 한다. 또한 예컨대 scanf(“%d\n”)를 사용할 때 일어날 수 있는 것처럼, 표준 입력을 읽을 때 실수로 블로킹되는 것을 피해야 한다. 올바른 방법은 기술 안내문을 참조하시오.
GRADING
총 30점에 해당하는 여러 테스트에서 R은 500을 넘지 않는다.
총 55점에 해당하는 여러 테스트에서는 어떤 지역도 직원이 500명을 넘지 않는다.
위 두 조건이 모두 성립하는 테스트는 15점에 해당한다.
두 조건 중 적어도 하나가 성립하는 테스트는 70점에 해당한다.