루미 알고리즘

#1511플래티넘Reinventing Mathematics

PO 2021 결선코딩출제 Björn Magnusson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

TestcaseConstraints
1N=500,T=5000,k_i ≤ 3
2N=500,T=5000,k_i ≤ 30
3N=500,T=50000,k_i ≤ 3
4N=500,T=50000,k_i ≤ 30
5N=10^5,T=10^7,k_i ≤ 3
6N=10^5,T=10^7,k_i ≤ 30
7N=300,T=30000 and k_i=1 for all i ≠ 0.
8N=300,T=30000 and every theorem is needed to prove at most one other theorem.
9N=10^5,T=10^7 and k_i=1 for all i ≠ 0.
10N=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

출처 표기

출처: Programmeringsolympiaden 2021년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.