Задача : Связное соединение - C++ - Ответ 17227767

@Miffty · Регистрация: 26.02.2024

Author24 — интернет-сервис помощи студентам

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

Увлекшись этим открытием, Вова составил список из Q запросов для изучения кристалла, каждый из которых принадлежит к одному из двух типов.

Тип 1. Передать импульс частице v. При этом частица v и все с ней напрямую связанные частицы увеличивают свой счётчик на 1.
Тип 2. Узнать текущее значение счётчика у частицы v
Ваша задача как друга Вовы и эксперта в области программирования состоит в том, чтобы обработать эти запросы и помочь ему понять, как работает этот необычный кристалл.
Первая строка содержит три целых числа N, M и Q — количество частиц, количество связей между ними и количество запросов соответственно.
Следующие M строк описывают связи между частицами. Каждая строка содержит два целых числа: a и b (1≤a,b≤N,a не равно b) означающих, что частицы a и b напрямую связаны.
Следующие Q строк описывают запросы. Каждая строка содержит два целых числа: t и v (1≤t≤2,1≤v≤N) где t — тип запроса, а v — номер частицы.

Формат вывода
На каждый запрос типа 2 выведите строчку с одним числом - значением счётчика в указанной частице.

Ограничение времени - 1 секунда
Ограничение памяти - 64mb
#include <iostream>
#include <vector>

C++

using namespace std;
 
void processQuery(vector<vector<int>>& particles, vector<int>& counter, int t, int v) {
    if (t == 1) {
        
        counter[v]++;
        
        
        for (int i = 0; i < particles[v].size(); i++) {
            int connectedParticle = particles[v][i];
            counter[connectedParticle]++;
        }
    } else if (t == 2) {
        
        cout << counter[v] << endl;
    }
}
 
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    
    
    vector<vector<int>> particles(n + 1);
    
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        particles[a].push_back(b);
        particles[b].push_back(a);
    }
    
    
    vector<int> counter(n + 1, 0);
    
    
    for (int i = 0; i < q; i++) {
        int t, v;
        cin >> t >> v;
        
        processQuery(particles, counter, t, v);
    }
    
    return 0;
}

В этом коде при каких-то неизвестных мне вводных данных время было чуть больше секунды и я хз как это исправить

Вернуться к обсуждению:
Задача : Связное соединение C++

Следующий ответ

Другие темы раздела
C++ Задача: Реклама https://www.cyberforum.ru/ cpp-beginners/ thread3156601.html Чем больше шрифт на рекламном щите, тем дальше видно рекламу. Вам поручили следующую задачу. Есть текст рекламного объявления из N слов. Известен размер рекламного щита W×H Есть несколько правил размещения рекламных текстов. 1. Запрещено переносить слова. 2. Слова на одной строке необходимо разделять пробелом. 3. Текст занимает весь рекламный щит. Отступы от краев делать не надо. 4. Шрифт...	C++ Сколько раз в последовательности встречается подпоследовательность 4020 ? Однажды вы узнали об уникальной заброшенной библиотеке, которая находится в сердце древнего, покинутого города. Согласно легендам, библиотека хранит в себе множество тайных знаний, включая формулы магических заклинаний, записанные в виде числовых последовательностей. Одна из самых могущественных и загадочных последовательностей - это код 4020, который, как гласит предание, является ключом к...
C++ Задача: Шлёпа https://www.cyberforum.ru/ cpp-beginners/ thread3156593.html Мальчик Шлёпа получил на день рождения массив из целых чисел размера N. Шлёпа умеет делать единственную операцию над массивом - "шлёп". Он выбирает позицию pos(2≤pos≤N−1) и сортирует по возрастанию элементы в массиве в интервале . Помогите Шлёпе отсортировать массив по возрастанию не более, чем за N^2 шлёпов. Если существует несколько способов сделать это, - выведите любой из них. Формат ввода...	C++ Почему метод класса работает не так, как ожидалось https://www.cyberforum.ru/ cpp-beginners/ thread3156591.html EQ eq{coeff_a, coeff_b, coeff_c}; EQ* peq = &eq; peq->solution(); peq->get_record(); std::wcout << L'\t'; peq->show_roots(); Метод show_roots() работает не так, как ожидалось. Смотрел в отладчике, корни уравнения находятся и присваиваются соответствующим переменным. Когда вызывается show_roots(), то выводит в консоль значения корней nan. В некоторых...
Найти длину отрезка C++ Помогите написать программу на c++ Точки A и B заданы координатами на плоскости: A( x1 , у1 ), B( x2 , y2 ). Найти длину отрезка AB.	C++ Программа для определения стоимости билета в кинотеатре https://www.cyberforum.ru/ cpp-beginners/ thread3156513.html Подскажите, пожалуйста с выполнением кода. Сама задача звучит, напишите программу, которая запрашивает у пользователя возраст и день недели, в который он планирует посетить кинотеатр, и определяет стоимость билета в зависимости от этих параметров. Программа должна содержать структуру с switch
C++ Зачем использовать ссылки если есть указатели? https://www.cyberforum.ru/ cpp-beginners/ thread3156489.html Изучаю указатели и ссылки. Понял зачем нужны указатели и где их применять. Теперь не могу понять зачем нужны ссылки, если есть указатели. Ведь вместо того чтобы делать "псевдоним" jобъекта можно взять его адрес, а потом операцией разыменовывания присвоить переменной новое значение. Тоже самое с большими объектами. Просто сделать указатель на указатель или указатель на начало. Зачем усложнять и...	Определить вид треугольника. Оператор switch C++ Как с помощью оператора switch можно записать программу, которая запрашивает у пользователя длины трех сторон треугольника и определяет его вид ("Равносторонний", "Равнобедренный", "Прямоугольный" и "Обычный")? Возможно ли это? Например, если я в операторе switch записал следующую запись, то при выводе она выводит название того треугольника, название кейса которого я укажу. Как можно исправить,...
C++ Вычислить значение переменной t по заданной расчетной формуле https://www.cyberforum.ru/ cpp-beginners/ thread3156443.html Вычислить значение переменной t по заданной расчетной формуле и набору исходных данных. Значения исходных данных вводить с клавиатуры. На печать вывести значения вводимых исходных данных и результат вычислений, сопровождая вывод наименованием выводимых переменных	C++ Освобождение памяти двумерного массива https://www.cyberforum.ru/ cpp-beginners/ thread3156441.html Если я сделаю так: for (int i = 0; i < n; i++) delete Board; Надо ли мне делать так: delete Board;?
C++ Массив функций Здравствуйте. Изучил ссылки, указатели и массивы функций. Для закрепления материала решил написать небольшую прогу в которой вызывается вектор из двух функций (где в одну передается переменная по значению, а в другую по ссылке), но компилятор отказывается её запускать и не показывает ошибок, не могу понять в чем может быть дело. #include <iostream> #include <functional> #include <vector> ...	C++ Код не работает на <filesystem> https://www.cyberforum.ru/ cpp-beginners/ thread3156385.html #include <iostream> #include <vector> #include <map> #include <string> #include <clocale> #include <Windows.h> #include <stdio.h> #include <fstream> #include <regex>

	27.02.2024, 00:27