Milking Order
골드 II의견: 0
Farmer John's \(N\) cows (\(1 \leq N \leq 10^5\)), numbered \(1 \ldots N\) as always,
happen to have too much time on their hooves. As a result, they have worked out
a complex social hierarchy related to the order in which Farmer John milks them
every morning.
After weeks of study, Farmer John has made \(M\) observations about his cows'
social structure (\(1 \leq M \leq 50,000\)). Each observation is an ordered list
of some of his cows, indicating that these cows should be milked in the same
order in which they appear in this list. For example, if one of Farmer John's
observations is the list 2, 5, 1, Farmer John should milk cow 2 sometime before
he milks cow 5, who should be milked sometime before he milks cow 1.
Farmer John's observations are prioritized, so his goal is to maximize the value
of \(X\) for which his milking order meets the conditions outlined in the first
\(X\) observations. If multiple milking orders satisfy these first \(X\)
conditions, Farmer John believes that it is a longstanding tradition that cows
with lower numbers outrank those with higher numbers, so he would like to milk
the lowest-numbered cows first. More formally, if multiple milking orders
satisfy these conditions, Farmer John would like to use the lexicographically
smallest one. An ordering \(x\) is lexicographically smaller than an ordering \(y\)
if for some \(j\), \(x_i = y_i\) for all \(i < j\) and \(x_j < y_j\) (in other words,
the two orderings are identical up to a certain point, at which \(x\) is smaller
than \(y\)).
Please help Farmer John determine the best order in which to milk his cows.
Problem credits: Jay Leeds
Problem credits: Jay Leeds
The first line contains \(N\) and \(M\). The next \(M\) lines each describe an
observation. Line \(i+1\) describes observation \(i\), and starts with the number of
cows \(m_i\) listed in the observation followed by the list of \(m_i\) integers
giving the ordering of cows in the observation. The sum of the \(m_i\)'s is at
most \(200,000\).
Output \(N\) space-separated integers, giving a permutation of \(1 \ldots N\)
containing the order in which Farmer John should milk his cows.
milkorder.inmilkorder.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.
평가 및 의견
Milking Order
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Milking Order