Олимпиадный тренинг

Задача . D. Цветные порталы


Задача

Темы: Бинарный поиск графы жадные алгоритмы кратчайшие пути Перебор реализация Структуры данных *1600

На прямой расположено \(n\) городов. Города пронумерованы целыми числами от \(1\) до \(n\).

Для перемещения между городами используются порталы. Порталы бывают \(4\) цветов: синий, зеленый, красный и желтый. В каждом городе расположены порталы двух разных цветов. Из города \(i\) можно переместиться в город \(j\), если в них есть порталы одинакового цвета (например, между городом «красный-синий» и городом «синий-зеленый» можно перемещаться). Данное перемещение стоит \(|i-j|\) монет.

Ваша задача — ответить на \(q\) независимых запросов: посчитайте минимальную стоимость, чтобы переместиться из города \(x\) в город \(y\).

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа \(n\) и \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) — количество городов и количество запросов, соответственно.

Вторая строка содержит \(n\) строк одного из следующих типов: BG, BR, BY, GR, GY или RY; \(i\)-я из них описывает порталы, находящиеся в \(i\)-м городе; символ B обозначает, что в городе есть портал синего цвета, G — зеленого, R — красного, а Y — желтого.

\(j\)-я из следующих \(q\) строк содержит два целых числа \(x_j\) и \(y_j\) (\(1 \le x_j, y_j \le n\)) — описание \(j\)-го запроса.

Дополнительные ограничения на входные данные:

  • сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\);
  • сумма \(q\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Выходные данные

Для каждого запроса выведите одно целое число — минимальную стоимость, чтобы переместиться из города \(x\) в город \(y\) (или \(-1\), если это невозможно).


Примеры
№Входные данныеВыходные данные
1 2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2 
1
4
0
3
2
-1

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет