레이팅 미적용언제나처럼 \(1 \ldots N\)으로 번호가 매겨진 농부 존의 \(N\)마리 소들(\(1 \leq N \leq 10^5\))은 발굽 위의 시간이 너무 많이 남아돈다. 그 결과, 소들은 농부 존이 매일 아침 우유를 짜는 순서와 관련된 복잡한 사회적 위계를 만들어 냈다.
몇 주간의 연구 끝에 농부 존은 소들의 사회 구조에 관해 \(M\)개의 관찰 결과를 얻었다 (\(1 \leq M \leq 50,000\)). 각 관찰 결과는 소들 중 일부의 순서 있는 목록으로, 이 소들이 목록에 나오는 순서와 같은 순서로 착유되어야 함을 뜻한다. 예를 들어 농부 존의 관찰 결과 중 하나가 목록 2, 5, 1이라면, 농부 존은 소 5의 우유를 짜기 전 언젠가 소 2의 우유를 짜야 하고, 소 1의 우유를 짜기 전 언젠가 소 5의 우유를 짜야 한다.
농부 존의 관찰 결과들에는 우선순위가 있어서, 그의 목표는 착유 순서가 처음 \(X\)개의 관찰 결과에 명시된 조건을 만족하도록 하는 \(X\)의 값을 최대화하는 것이다. 처음 \(X\)개의 조건을 만족하는 착유 순서가 여러 개라면, 농부 존은 번호가 낮은 소가 번호가 높은 소보다 서열이 높다는 것이 오랜 전통이라고 믿으므로, 번호가 가장 낮은 소들을 먼저 착유하고 싶어 한다. 더 형식적으로, 이 조건들을 만족하는 착유 순서가 여러 개라면 농부 존은 사전순으로 가장 작은 것을 사용하고 싶어 한다. 순서 \(x\)가 순서 \(y\)보다 사전순으로 작다는 것은, 어떤 \(j\)에 대해 모든 \(i < j\)에서 \(x_i = y_i\)이고 \(x_j < y_j\)인 것이다(다시 말해, 두 순서는 어떤 지점까지 동일하고 그 지점에서 \(x\)가 \(y\)보다 작다).
농부 존이 소들의 우유를 짤 최선의 순서를 정하도록 도와주자.
출제자: Jay Leeds
출제자: Jay Leeds
첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(M\)개의 줄에는 각각 관찰 결과가 하나씩 주어진다. \(i+1\)번째 줄은 관찰 결과 \(i\)를 나타내며, 그 관찰 결과에 나열된 소의 수 \(m_i\)로 시작하고, 이어서 관찰 결과에서의 소들의 순서를 나타내는 정수 \(m_i\)개가 주어진다. \(m_i\)들의 합은 최대 \(200,000\)이다.
농부 존이 소들의 우유를 짜야 할 순서를 담은 \(1 \ldots N\)의 순열을, 공백으로 구분된 정수 \(N\)개로 출력한다.
milkorder.in · 출력을 쓸 파일 milkorder.out4 3
3 1 2 3
2 4 2
3 3 4 11 4 2 3Here, Farmer John has four cows and should milk cow 1 before cow 2 and cow 2
before cow 3 (the first observation), cow 4 before cow 2 (the second
observation), and cow 3 before cow 4 and cow 4 before cow 1 (the third
observation). The first two observations can be satisfied simultaneously, but
Farmer John cannot meet all of these criteria at once, as to do so would require
that cow 1 come before cow 3 and cow 3 before cow 1.
This means there are two possible orderings: 1 4 2 3 and 4 1 2 3, the first
being lexicographically smaller.