Мой дед

Заметим, что если в $$$k$$$-й день ответ «YES», то существует путь от $$$1$$$ до $$$N$$$, что для каждой тропинке $$$i$$$ на этом пути соблюдается неравенство $$$s_i \cdot a_k > w_i \cdot b_k \Leftrightarrow \frac{a_k}{b_k} > \frac{w_i}{s_i}$$$. Давайте для каждого ребра запомним величину $$$\frac{w_i}{s_i}$$$. По этой величине можно определить, существует ли путь в $$$k$$$-й день: мысленно удалим все рёбра, для которых $$$\frac{w_i}{s_i} \ge \frac{a_k}{b_k}$$$. Если после этого путь от $$$1$$$ до $$$N$$$ существует, то ответ в этот день «YES», иначе «NO».

Теперь рассмотрим для каждого дня $$$j$$$ значение $$$d_j = \frac{a_j}{b_j}$$$. Отсортируем все дни по этому значению. Если рассматривать их в порядке возрастания и так же мысленно удалять рёбра, то можно считать, что в этом порядке в графе появляются новые рёбра, а старые всегда остаются. Это значит, что для каких-то первых нескольких дней в этом порядке (возможно, ни для каких) ответ «NO», а для всех остальных (возможно, ни для каких) — «YES». Поэтому можно сделать бинарный поиск по дням и найти эту границу. Для проверки нужно строить новый граф, удалять не подходящие рёбра и проверять существование пути от $$$1$$$ до $$$N$$$ поиском в глубину или в ширину. Мы получим величину $$$\frac{a}{b}$$$ такую, что на все дни с $$$\frac{a_j}{b_j} \le \frac{a}{b}$$$ ответ «NO», а для остальных — «YES». После этого выведем ответ в исходном порядке. Сложность такого решения равна $$$O((N + M + Q) \cdot \log Q)$$$.

Альтернативное решение

Отсортируем рёбра по величине $$$\frac{s_j}{w_j}$$$. Поскольку на каждой полянке грибы и ягоды продаются по одной и той же цене, то для проверки корректности пути достаточно запомнить ребро с самым маленьким соотношением $$$\frac{s_j}{w_j}$$$.

Воспользуемся динамическим программированием $$$dp[v]$$$ — наименьшее ребро на лучшем пути до $$$v$$$. Под наименьшим ребром мы подразумеваем номер ребра с наименьшим значением $$$\frac{s_j}{w_j}$$$ в порядке сортировки. Массив $$$dp[v]$$$ можно заполнить в порядке топологической сортировки графа, это похоже на алгоритм Дейкстры на минимум.

Пусть $$$dp[N] = e$$$, то есть в лучшем пути до $$$N$$$-й вершины обязательно встретится ребро $$$e$$$ или хуже. Это значит, что мы гарантированно пройдём по ребру с соотношением $$$\frac{s_j}{w_j}$$$ не лучше $$$\frac{s_e}{w_e}$$$. По формуле из первого решения получим, что для $$$k$$$-го дня ответ «YES», если $$$\frac{a_k}{b_k} > \frac{s_e}{w_e}$$$. Это позволяет нам сразу отвечать на все запросы. Сложность такого решения равна $$$O(N + M \cdot \log M + Q)$$$.