레이팅 미적용농부 존에게는 \(N\)개의 헛간이 있고 (\(3\le N\le 5\cdot 10^5\)), 그중 서로 다른 \(K\) (\(3\le K\le N\))쌍의 헛간이 연결되어 있다.
먼저 애너벨이 각 헛간에 \([1,N]\) 범위의 서로 다른 정수 라벨을 붙이고, 라벨이 \(a_1,\dots,a_K\)인 헛간들이 그 순서대로 사이클을 이루며 연결되어 있음을 관찰한다. 즉, 모든 \(1\le i
다음으로 베시도 각 헛간에 \([1,N]\) 범위의 서로 다른 정수 라벨을 붙이고, 라벨이 \(b_1,\dots,b_K\)인 헛간들이 그 순서대로 사이클을 이루며 연결되어 있음을 관찰한다. 모든 \(b_i\)는 서로 다르다.
일부 헛간(하나도 없거나 전부일 수도 있다)은 애너벨과 베시가 같은 라벨을 붙였을 수 있다. 애너벨과 베시가 같은 라벨을 붙인 헛간 수의 최댓값을 구하라.
문제 제공: Benjamin Qi
채점 방식
- 입력 4-5: \(N \le 8\)
- 입력 6-8: \(N \le 5000\)
- 입력 9-15: 추가 제약 조건 없음
문제 제공: Benjamin Qi
첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 줄에 \(a_1,\dots, a_K\)가 주어진다.
다음 줄에 \(b_1,\dots, b_K\)가 주어진다.
고정점의 최대 개수를 출력한다.
6 3
1 2 3
2 3 16Annabelle and Bessie could have assigned the same label to every barn.
6 3
1 2 3
4 5 60Annabelle and Bessie could not have assigned the same label to any barn.
6 4
1 2 3 4
4 3 2 54Annabelle and Bessie could have assigned labels \(2,3,4,6\) to the same barns.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Silver