영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Oh no, all mathematics has disappeared! How did this happen? You don't have time to ponder over it, instead you realize that you must reinvent as much mathematics as possible before the world ends! Although all actual knowledge has vanished, you know a little about mathematics. Mathematics is composed of N theorems. Each theorem, i, depends on a number of theorems a_{i_1}, a_{i_2}, …, a_{i_k} < i, which must be proven before one can start with the theorem. To prove theorem i you need to spend t_i time. The value of a proven theorem is v_i.
You have T time. Choose which theorems you should prove to maximize the total value of the mathematics you have time to reinvent.
Input
The first line contains an integer C (0 ≤ C ≤ 10), the number of the test case (0 is the example case below).
The second line contains two integers: N (1 ≤ N ≤ 10^5) and T (1 ≤ T ≤ 10^7).
Then follows N descriptions of theorems. A description of a theorem consists of two rows. First comes a row with the integers t_i, v_i and k_i (0 ≤ t_i, v_i ≤ 10^4, 0 ≤ k_i ≤ N). Then comes a row with k_i integers: a_{i_1}, a_{i_2}, …, a_{i_k} < i, the indices of the theorems that must be proven before this theorem. Theorems are indexed from 0 in the order they appear in the input.
Output
First print an integer S (0 ≤ S ≤ N), the number of theorems that you will prove.
On the next line, print S integers, the theorems that you will prove in the order that you will prove them.
Points
Your program will be tested on 10 test cases and scored based on how it performs relative to the judges' solution. If your submission on a given test case achieves a total value of theorems equal to X, and the total value the judges have achieved on that test case is Y, then your score on that test case will be min(10, 10 · (X / Y)^3), rounded to two decimal places.
Your score for a submission is the sum of the scores for the test cases, and your total score is the score for the best submission. Thus, it is not possible to combine test cases between different submissions; instead, you must submit a single program that maximizes your score on all test cases simultaneously.
The example test case will always give 0 points.
Test cases
Under attachments at the bottom of the page, you can download testcases generated in the same way as the real testcases, but using a different random seed (https://en.wikipedia.org/wiki/Random_seed).
The 10 testcases are described below.
| Testcase | Constraints |
|---|---|
| 1 | N=500,T=5000,k_i ≤ 3 |
| 2 | N=500,T=5000,k_i ≤ 30 |
| 3 | N=500,T=50000,k_i ≤ 3 |
| 4 | N=500,T=50000,k_i ≤ 30 |
| 5 | N=10^5,T=10^7,k_i ≤ 3 |
| 6 | N=10^5,T=10^7,k_i ≤ 30 |
| 7 | N=300,T=30000 and k_i=1 for all i ≠ 0. |
| 8 | N=300,T=30000 and every theorem is needed to prove at most one other theorem. |
| 9 | N=10^5,T=10^7 and k_i=1 for all i ≠ 0. |
| 10 | N=10^5,T=10^7 and every theorem is needed to prove at most one other theorem. |
예제
예제 1
0 5 11 1 1 0 2 7 1 0 4 2 1 0 5 1 1 0 1 10 2 2 3
4 0 2 3 4