2026 年 USACO竞赛 第二场比赛银奖组问题二—Declining Invitations

N contestants participated in a contest, each placing a distinct rank from 1
to N. There are C criteria used to invite contestants to participate in the final round, and the ith-ranked contestant satisfies a specified ni of them (1≤ni ≤C).

The invitation process runs as follows. First, the top f1 students who satisfy the 1
st criteria will be invited. Then, out of all students who haven't yet been invited, the top f2 (or all remaining if there are fewer than f2 remaining) students who satisfy the 2nd criterion will be invited. This process repeats, for each i
from 1 to C (1≤fi≤N).

However, some contestants will decline to participate in the final round, in which case they will be ignored when determining who to invite.

You are given a permutation p1,p2,…,pN of 1…N. For each i from 0 to N−1, determine the sum of the ranks of the contestants who will be invited if the participants with ranks given by the first i elements of p decline to attend.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and C (1≤N,C≤105).

The next line contains f1,f2,…,fC.

The next line contains p1…,pN.

The next N lines each contain ni (1≤ni≤C), followed by ni distinct integers in [1,C], representing the criteria that the i th-ranked contestant satisfies. It is guaranteed that ∑ni≤106.

OUTPUT FORMAT (print output to the terminal / stdout):

Output N lines, the sum of ranks of invitees before each declination.

SAMPLE INPUT:

5 1
3
5 1 3 2 4
1 1
1 1
1 1
1 1
1 1

SAMPLE OUTPUT:

6
6
9
6
4

There is only one criterion. The top three remaining contestants who have not declined will be invited.

SAMPLE INPUT:

5 4
1 1 1 1
1 2 3 4 5
1 1
2 1 2
2 2 3
2 3 4
1 4

SAMPLE OUTPUT:

10
14
12
9
5

Initially, the ith contestant gets invited under criterion i for all 1≤i≤4.

After the first declination, the i+1th contestant gets invited under criterion i for all 1≤i≤4.

SAMPLE INPUT:

6 10
5 6 4 1 3 3 3 6 5 3
1 4 6 5 2 3
1 9
5 4 3 9 5 10
10 6 2 10 1 7 8 3 9 4 5
10 4 5 3 1 2 9 10 6 7 8
2 3 1
8 1 9 7 4 3 10 6 2

SAMPLE OUTPUT:

21
20
16
10
5
3

SCORING:

Inputs 4-6: N,C≤103,∑ni≤104
Inputs 7-8: C=1
Inputs 9-10: C=2
Inputs 11-16: No additional constraints.

Problem credits: Benjamin Qi

历年学员USACO获奖战绩一览

2026赛季5位铂金级
2024-2025赛季5位铂金级
20238位铂金级

USACO 历年战绩

2026赛季战绩

  • 5位铂金级
  • 22位金级
  • 25位银级

2024–2025赛季战绩

翰林考点及辅导学生

  • 5位铂金级
  • 25位金级
  • 38位银级

2023–2024赛季战绩

  • 8位铂金级
  • 32位金级
  • 37位银级

2022–2023赛季战绩

  • 10位铂金级
  • 29位金级
  • 71位银级

篇幅有限,仅展示部分年份战绩。

在线咨询
微信咨询