| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 59 | 23 | 22 | 47.826% |
DGIST 나라에는 $N$명의 비밀 요원이 있다. 모든 요원들은 1ドル$이상 $N$이하의 고유한 번호로 불린다. 당국은 요원들에게 등급을 붙이며, $i$번 요원의 등급은 $a_i$이다.
DGIST 나라의 비밀 요원들은 보안 연락망을 통해 서로 소통할 수 있다. 이런 보안 연락망은 총 $M$개 존재하며, 요원 $u$와 요원 $v$를 연결하는 형식이다. DGIST 나라의 요원들은 직접적인 연락망으로 연결되어 있지 않더라도 여러 요원들을 거쳐 원활히 소통할 수 있다. 예를 들어, 요원 1ドル$과 요원 2ドル,ドル 요원 2ドル$와 요원 3ドル$이 각각 하나의 보안 연락망으로 연결되어 있다면, 요원 1ドル$과 요원 3ドル$도 서로 소통할 수 있다. 이때 두 요원은 소통하기 위해 2ドル$개의 보안 연락망을 이용한다. 또한, 비밀 요원들이 작전에 투입된 경우, 작전에 투입되지 않은 요원과 연결된 보안 연락망은 이용할 수 없게 된다.
DGIST 나라의 정보부 DSIS는 비밀 작전을 계획하고 있다. DSIS는 작전을 위한 요원들을 모집하려고 한다. 작전에 모집된 모든 요원들은 서로 소통할 수 있어야 하며, 이를 만족하여 구성된 팀의 작전 수행 능력은 (팀에 속한 요원 수)$\times$(팀에 속한 요원들의 등급 중 최솟값) 이다. DSIS는 팀의 작전 수행 능력이 정확히 $X$일 때 가장 효율적으로 계획중인 작전을 수행할 수 있다고 판단했다.
DSIS에서 비밀 작전을 위한 팀 구성 임무를 맡은 달구는, 작전 수행 능력이 정확히 $X$인 팀을 구성할 수 있는지 판단해야 한다. 그러나 DGIST 나라의 비밀 요원들은 자주 말썽을 일으켜 제명 처분을 받으며, 제명된 요원은 이후 그 어떤 비밀 작전에도 참여할 수 없다. 그렇기에 달구는 요원이 제명될 때 마다 눈물을 머금고 작전 수행 능력이 정확히 $X$인 팀을 구성할 수 있는지를 다시 판단한다.
총 $Q$명의 요원들이 한 명씩 제명 처분을 받게 되었을 때, 달구가 각 제명 처분 이후에 작전 수행 능력이 정확히 $X$인 팀을 구성할 수 있는지 여부를 구하여라.
첫째 줄에 비밀 요원의 수 $N,ドル 보안 연락망의 수 $M,ドル 요구 작전 수행 능력 $X$가 공백으로 구분되어 정수로 주어진다. (1ドル\leq N \leq 100,000円$; 0ドル \leq M\leq 100,000円$; 1ドル\leq X\leq 10^{18}$)
둘째 줄에 각 요원의 등급 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 정수로 주어진다. (1ドル\leq a_i\leq 10^{13}$)
다음 $M$개의 줄에 걸쳐 비밀 요원의 번호 $u_i, v_i$가 공백으로 구분되어 주어진다. (1ドル \leq u_i < v_i \leq N$) 이는 $u_i$번 요원과 $v_i$번 요원이 하나의 보안 연락망으로 소통할 수 있다는 의미이다. 이미 주어진 요원 쌍이 다시 주어지는 경우는 없다.
다음 줄에 제명 처분을 받은 총 요원의 수 $Q$가 주어진다. (1ドル\leq Q\leq N$)
다음 $Q$개의 줄에 걸쳐, 제명 처분을 받은 요원의 번호 $q_i$가 주어진다. (1ドル \leq q_i \leq N$) 동일한 요원에 대한 제명 처분은 여러 번 주어지지 않으며, 제명 처분을 받은 순서대로 주어진다.
각 제명 처분에 대해, 작전 수행 능력이 정확히 $X$인 팀을 구성할 수 있으면 1ドル,ドル 아니면 0ドル$을 한 줄에 하나씩 출력한다.
4 4 6 2 3 3 2 1 2 2 3 3 4 1 3 2 1 2
1 0
University > DGIST > 2025 DGIST 알고리즘 경진대회 F번