양방향 그래프로 보고, 한 간선을 이용하면 다음에 탈 간선은 자동으로 정해진다.
그러므로 간선을 정점으로 하는 그래프를 만들면, 각 정점의 outdegree는 $1$이다.
따라서 이 그래프에는 사이클이 $1$개만 있을 수 있다. 시작점은 처음 그래프에서 각 정점에 연결된 길들 중 가장 아름다운 길들이다.
P와 연결된 길 중 가장 아름다운 길을 $e$라고 하자.
그러면 도착점은 $e$를 통해 $P$로 들어오는 경우, 다른 길로 들어오는 경우가 있다. 그런데 다른 길로 들어올 경우 무조건 $e$로 나가게 된다. 따라서 $e$로 나가는 경우 하나로 묶어 처리하면, 두 개의 도착점만 처리하면 된다. 두 개의 도착점을 따로 처리하자.
1) 도착점이 사이클에 속하지 않는 경우
어디서 출발하던 거리는 고정이다. 거리는 $2M$ 이하이므로 배열에 담아두면 쿼리당 $O(1)$에 처리할 수 있다.
2) 도착점이 사이클에 속하는 경우
사이클의 길이를 $c$라고 하면, 최단거리가 $G-ct$ ($t$는 음이 아닌 정수)인 시작점들은 모두 가능하다.
$c$로 나눈 나머지에 따라서 따로 전처리를 해두면, $O(1)$에 쿼리를 구할 수 있다.
시간복잡도는 $O(N+M+Q)$.
간단한 문제이다.
무조건 논 위에 쌀 창고가 있는 최적해가 존재한다. 논 사이에 창고가 있다면, 옆의 논으로 옮기는 것이 이득이다.
$L$번 논부터 $R$번 논까지 사용한다면, 창고가 $\lfloor \frac{L + R}{2}\rfloor$번 논에 있을 때 최적해이다.
$\lfloor \frac{L + R}{2}\rfloor$를 고정하고, $ans$가 답이 될 수 있는지 확인하는 것은 prefix sum을 전처리해두면 $O(1)$에 구해진다.
$\lfloor \frac{L + R}{2}\rfloor$에서 $ans + 1$이 가능한지 확인하고, 가능하다면 $ans$를 1 늘린다. 불가능하다면 $\lfloor \frac{L + R}{2}\rfloor$를 1 늘린다. 이것을 반복하면 $O(R)$에 $ans$의 최대값을 구할 수 있다.
이것이 가능한건 $\lfloor \frac{L + R}{2}\rfloor$가 고정되었을 때 $ans$가 가능하다면, $ans$보다 작은 값도 무조건 가능하기 때문이다.
시간복잡도는 $O(R)$.