| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 2048 MB | 20 | 18 | 17 | 89.474% |
A celebrity in a social network is somebody with many followers, but who doesn't follow them back. More precisely, a person is a celebrity for a group of people, if
The celebrity centrality of person $v$, written $\mathrm{CC}(v)$, is the maximum size of such a group.
We model the social network as a directed graph with $N$ vertices $1$, $\ldots$, $N$. A directed edge from $u$ to $v$ means that person $u$ follows person $v$. For example, in
we have $\operatorname{CC}(1) = 0$, $\operatorname{CC}(2) = 1$, and $\operatorname{CC}(5) = 2$.
Your task is to find a vertex $v$ with the maximum celebrity centrality $\mathrm{CC}(v)$. In case of a tie, choose the smallest $v$.
The input consists of
Output two integers: the smallest $v$ with the maximum celebrity centrality and the value $\mathrm{CC}(v)$.
6 8 1 2 2 1 2 3 3 2 3 6 4 5 5 2 6 5
5 2
1 0
1 0
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2025 I번