시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 100 58 52 69.333%

문제

MOLOCO, a global company with an unbeatable global reach, is developing a new survey platform to increase user engagement.

There are $N$ people who want to vote on an issue. Each person is either in support of the issue or against the issue.

There are $M$ not necessarily disjoint sets of people $S_1, S_2, \cdots, S_M$. For these $M$ sets and a constant $p$ ($0 \le p \le 1$), the propositions below are established.

  • For every set $S_i$, at least $p \cdot|S_i|$ people belonging to $S_i$ is in support of the issue.

If $p = 0$, no information can be obtained from this proposition. $p = 1$ shows that everyone is in support of the issue. That is, as $p$ grows, it becomes easier to ascertain who is in support of the issue.

Thus, if a proposition is established for a sufficiently large $p$, we can know that everyone is in support of the issue. Find the maximum value of $p$ such that you can not be certain everyone is in support.

입력

The first line contains two integers $N$ and $M$, where $N$ denotes the number of people and $M$ denotes the number of sets.

The next $M$ lines describe the information of each of the $M$ sets.

The $i$-th line starts with an integer $|S_i|$, denoting the number of elements in the set $S_i$, followed by $|S_i|$ distinct integers $S_{i,j}$, denoting the elements in the set $S_i$.

출력

Output the maximum value of $p$ such that you cannot be certain everyone is in support of the issue.

Your answer will be considered correct if it has an absolute or relative error less than $10^{-6}$.

제한

  • $1 \le N,M \le 200\,000$
  • $S_i \subseteq \{1,2,\cdots,N\}$ $(1 \le i \le M)$
  • $\sum_{i=1}^{M}|S_i| \le 1\,000\,000$
  • Everyone appears in at least one set.

서브태스크 1 (10점)

This subtask has additional constraints:  

  • $N \le 10$
  • $M \le 500$

서브태스크 2 (15점)

This subtask has an additional constraint:  

  • $N,M \le 500$

서브태스크 3 (75점)

This subtask has no additional constraints.

예제 입력 1

3 3
1 1
1 2
1 3

예제 출력 1

0

예제 입력 2

4 2
2 1 2
2 3 4

예제 출력 2

0.5

예제 입력 3

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

예제 출력 3

0.833333333

노트

In example 2, the proposition can be established for $p=0.5,$ if people 1, 3 are for and people 2, 4 are against.

However, if the proposition is established for $p>0.5, $ it is a contradiction to the proposition if there exists a person against an issue.

출처

University > KAIST > 2021 KAIST RUN Spring Contest C번

채점 및 기타 정보

  • 예제는 채점하지 않는다.