6 Задача с codeforses на разные темы (ссылки для проверки к каждой задаче)

Тема: Деревья отрезков

1.Минимумы на отрезках
ограничение по времени на тест
3 секундыограничение по памяти на тест
256 мегабайтввод
Задан числовой массив A[1..N]. Необходимо выполнить M операций вычисления минимального элемента на отрезке [L, R].


Входные данные
Первая строка входных данных содержит число N – размер массива.

Во второй строке записаны N чисел – элементы массива.

Третья строка содержит число M – количество запросов минимума.

Следующие M строк содержат пары чисел L и R (L ≤ R ≤ N), описывающие отрезки. Все числа во входных данных натуральные, не превосходящие 105.

Выходные данные
Для каждого запроса выведите найденный минимум.

входные данные
5
3 1 8 7 9
2
1 3
3 5

выходные данные
1
7
link https://codeforces.com/group/50U9rD7F6W/contest/31...

2.Суммы на отрезках
ограничение по времени на тест
1 секунда ограничение по памяти на тест 256 мегабайт

Задан числовой массив A[1..N]. Необходимо выполнить M операций, где каждая операция может быть двух видов:

1. вывести сумму всех элементов на отрезке [L, R],
2. присвоить элементу A[i] новое значение V.

Входные данные
Первая строка входных данных содержит число N – размер массива.

Во второй строке записаны N чисел – элементы массива.

Третья строка содержит число M – количество запросов.

Следующие M строк содержат по три целых числа. Первое число T задаёт тип операции: 1, если нужно найти сумму на отрезке, 2 – если нужно поменять элемент. Далее идут два числа, смысл которых зависит от T:

• Если T = 1, то последующие два числа L и R задают отрезок, сумму на котором надо найти.
• Если T = 2, то последующие два числа i и V задают позицию и новое значение элемента.

Ограничения: все числа во входных данных натуральные, не превосходящие 105. Также 1 ≤ L ≤ R ≤ N, 1 ≤ i ≤ N.

Для каждого запроса первого типа выведите на отдельной строке найденную сумму.

входные данные
4
3 1 8 7
3
1 1 3
2 2 5
1 1 3
выходные данные
12
16
link https://codeforces.com/group/50U9rD7F6W/contest/31...

Тема: Обходы, остовные деревья и потоки в графах

1.Удаление клеток
граничение по времени на тест
1 секунда ограничение
по памяти на тест256 мегабайт
Входные данные
В первой строке входных данных записаны два целых числа M и N — высота и ширина листа соответственно (1 ≤ M, N ≤ 500).

Далее идут M строк по N символов в каждой. Клетка представлена символом '#', вырезанная клетка — символом '.'.

Выходные данные
Выведите одно целое число — искомое количество частей.

Система оценки
Подзадача 1 : M, N ≤ 10

входные данные
5 8
#.###.##
##.#.###
###....#
##.#.###
#.###.##
выходные данные
4
link https://codeforces.com/group/50U9rD7F6W/contest/37...

2. Двудольный граф
Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.


Входные данные
Во входных данных вначале записано число N – количество вершин графа (1 ≤ N ≤ 100). Далее идёт матрица смежности размером N × N из нулей и единиц (0 обозначает отсутствие ребра, 1 – наличие). Граф неориентированный, без петель.

Выходные данные
В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет).

В случае ответа YES во второй строке выведите N чисел – цвета, в которые нужно раскрасить вершины. В случае нескольких верных ответов выведите любой.

входные данные
3
0 1 1
1 0 1
1 1 0
выходные данные
NO

входные данные
3
0 1 1
1 0 0
1 0 0
выходные данные
YES
1 2 2

входные данные
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
выходные данные
NO
link https://codeforces.com/group/50U9rD7F6W/contest/37...

3.Нуль-транспортировка
ограничение по времени на тест
1 секунда ограничение по памяти на тест64 мегабайта

космическом содружестве имеется N населённых планет. Планеты расположены в разных звёздных системах, поэтому перелёты между ними на корабле даже с околосветовой скоростью могут занимать годы и годы ...
К счастью, недавно учёные открыли способ создания двусторонних гиперпорталов, перемещение через которые происходит почти мгновенно! Однако, у порталов есть два минуса:

• во-первых, не любую пару планет можно соединить порталом;
• во-вторых, строительство портала – дело весьма затратное. А бюджет содружества, как известно, не резиновый.

Правительство решило узнать, какую наименьшую сумму придётся выделить из бюджета на строительство порталов, чтобы в итоге от каждой планеты можно было добраться до любой другой (возможно, с пересадками). Напишите программу, решающую данную задачу.


Входные данные
В первой строке входных данных записаны два числа N и M через пробел – общее количество планет и количество пар планет, между которыми есть возможность построить портал.

В каждой из следующих M строк записаны по три числа через пробел – номера планет и стоимость строительства портала между ними.

Ограничения: 1 ≤ N ≤ 1000, 1 ≤ M ≤ N·(N - 1) / 2, все стоимости – целые числа в интервале от 1 до 1000.

Выходные данные
Выведите одно число – минимальную суммарную стоимость порталов. Если же все планеты связать между собой невозможно, то выведите -1.

входные данные
4 5
1 2 3
1 3 4
2 3 2
2 4 1
3 4 8

выходные данные
6
link https://codeforces.com/group/50U9rD7F6W/contest/37...

Тема :Алгоритмы, основанные на обходах графов

Одностороннее движение
ограничение по времени на тест
1 секунда ограничение по памяти на тест
256 мегабайт

В некотором городе очень узкие улицы, поэтому в городе организовано одностороннее движение. Но в связи с ремонтными работами по расширению дорог некоторые улицы перекрыты для проезда. На рисунке изображён пример расположения площадей и оставшихся улиц с указанным направлением движения.

Требуется найти количество областей, на которые стал разбит город - таких, что в каждой области с любой площади можно доехать до любой другой. В данном примере такими областями являются множества {1,2,3}, {4} и {5,7,6}, при этом ответ будет 3.


Входные данные
В первой строке количество площадей N (1 ≤ N ≤ 104) и количество дорог M (0 ≤ M ≤ 105). В каждой из следующих M строк записаны два числа ui и vi – начало и конец i-й дороги.

Выходные данные
Количество областей, на которые разбит город.

входные данные
7 10
1 2
2 3
2 5
2 4
3 1
3 4
4 5
5 7
6 5
7 6
выходные данные
3

входные данные
1 0
выходные данные
1
link https://codeforces.com/group/50U9rD7F6W/contest/32...