Задача №114318. Траффик
Центр Гдынии расположен на острове посередине реки Кацза. Каждое утро тысячи машин едут из жилых районов на западном берегу в индустриальные на восточном.
Остров можно представить в виде прямоугольника \(A\times B\) со сторонами, параллельными осям координат, углами \((0, 0)\) и \((A, B)\).
На острове есть \(n\) перекрёстков, пронумерованных натуральными числами от \(1\) до \(n\). Перекрёсток номер \(i\) имеет координаты \((x_i, y_i)\). Если координаты какого-то перекрёстка имеют вид \((0, y)\), то он находится на западном берегу, если \((A, y)\) - на восточном. Перекрёстки соединены дорогами, каждая - отрезок на плоскости, они не пересекаются (кроме концов). Дороги бывают односторонними и двусторонними. Нет никаких мостов и туннелей! Некоторые дороги могут идти по краям прямоугольника.
Поскольку плотность траффика растёт, мэр города нанял Вас (кого же ещё) проверить, достаточно ли текущей сети дорог. Он попросил написать программу, которая по карте города определит для каждого перекрёстка на западном берегу, сколько из него достижимых на восточном.
В первой строке входных данных дано четыре целых числа \(n\), \(m\), \(A\) и \(B\) (\(1\leq n\leq 300 000\), \(0\leq m\leq 900 000\), \(1\leq A\leq 10^9\), \(1\leq B\leq 10^9\). Это количества перекрёстков, дорог и размеры города, соответственно.
В каждой из следующих \(n\) строк есть два целых числа \(x_i\), \(y_i\) (\(0\leq x_i\leq A\), \(0\leq y_i\leq B\)), описывающих координаты перекрёстка номер \(i\). Перекрёстки не совпадают.
Следующие \(m\) строк описывают дороги, каждая одну. Это описание состоит из трёх чисел: \(c_i\) - номер перекрёстка, откуда (\(1\leq c_i\leq n\)), \(d_i\) - куда (\(1\leq d_i\leq n\)), \(k_i\in\{1, 2\}\) - тип дороги (сколькосторонняя). Разные дороги соединяют разные неупорядоченные пары перекрёстков.
Есть хотя бы один перекрёсткок на западном берегу, из которого можно добраться хотя бы в один на восточном по дорогам.
Выведите для каждого перекрёстка на западном берегу в своей строчке количество достижимых из него перекрёстков на восточном берегу.
Выводите в порядке уменьшения \(y\)-координаты.
1. (30 баллов) \(n, m\leq 6 000\).
2. (70 баллов) \(n\leq 300 000\), \(m\leq 900 000\).
5 3 1 3 0 0 0 1 0 2 1 0 1 1 1 4 1 1 5 2 3 5 2
2 0 2
12 13 7 9 0 1 0 3 2 2 5 2 7 1 7 4 7 6 7 7 3 5 0 5 0 9 3 9 1 3 2 3 2 1 3 4 1 4 5 1 5 6 1 9 3 1 9 4 1 9 7 1 9 12 2 10 9 1 11 12 1 12 8 1 12 10 1
4 4 0 2