Одним уютным вечером Алиса решила сыграть в классическую игру «Соедини точки», но с…
- User
Одним уютным вечером Алиса решила сыграть в классическую игру «Соедини точки», но с подвохом.
Чтобы начать игру, Алиса рисует прямую линию и отмечает на ней n точек, проиндексированных числами от 1 до n . Изначально между точками нет рёбер, так что все они попарно не соединены. Затем Алиса выполняет m операций следующего типа:
Она выбирает три целых числа ai , di (1≤di≤10 ) и ki . Затем для точек ai,ai+di,ai+2di,ai+3di,…,ai+ki⋅di Алиса соединяет ребром каждую пару из них. Алиса хочет узнать, сколько компонент связности† образуют эти точки после выполнения всех m операций.
† Считается, что две точки лежат в одной компоненте связности, если между ними есть путь, использующий несколько (возможно, ноль) промежуточных рёбер и вершин.
Входные данные Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤105 ) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа n и m (1≤n≤2⋅105 , 1≤m≤2⋅105 ).
В i -й из следующих m строк содержится три целых числа ai , di и ki (1≤ai≤ai+ki⋅di≤n , 1≤di≤10 , 0≤ki≤n ).
Гарантируется, что сумма значений n , а также сумма значений m по всем наборам входных данных не превосходит 2⋅105 каждая.
Выходные данные Для каждого набора входных данных выведите количество компонент связности.
Пример Входные данныеСкопировать 3 10 2 1 2 4 2 2 4 100 1 19 2 4 100 3 1 2 5 7 2 6 17 2 31 Выходные данныеСкопировать 2 96 61 Примечание В первом наборе входных данных есть n=10 точек. Первая операция соединяет точки 1 , 3 , 5 , 7 и 9 . Вторая операция соединяет точки 2 , 4 , 6 , 8 и 10 . В итоге получаем две компоненты связности: {1,3,5,7,9} и {2,4,6,8,10} .
Во втором наборе входных данных есть n=100 точек. Единственная операция соединяет точки 19 , 21 , 23 , 25 и 27 . Теперь они образуют одну компоненту связности размера 5 . Остальные 95 точек ни с кем не соединены, так что каждая из них образует отдельную компоненту связности. Значит, ответ равен 1+95=96 .
В третьем наборе входных данных есть n=100 точек. После выполнения всех операций все точки с нечётными номерами от 1 до 79 образуют одну компоненту связности размера 40 . Остальные 60 точек ни с кем не соединены, так что каждая из них образует отдельную компоненту связности. Значит, ответ равен 1+60=61 .
реши на C++. Тут нужен ОЧЕНЬ продвинутый и сложный алгоритм. используй однобуквенные переменные, олимпиадный стиль
- Assistant
#include <bits/stdc++.h> using namespace std; struct UF { vector<int> parent; UF(int n){ parent.resize(n+1); for(int i=0;i<=n;i++) parent[i]=i; } int find_set(int x){ return parent[x]==x ? x : parent[x]=find_set(parent[x]); } void union_set(int x, int y){ int fx = find_set(x); int fy = find_set(y); if(fx != fy){ parent[fx] = fy; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ int n, m; cin>>n>>m; UF uf(n); // Initialize L[d][r] for d=1 to10, r=0 tod-1 vector<vector<vector<int>>> L(11); // L[1..10][0..d-1] for(int d=1; d<=10; d++) { L[d].resize(d, vector<int>()); } for(int i=0;i<m;i++){ int a, d, k; cin>>a>>d>>k; // According to constraints, a +k*d <=n // If k ==0, single point, no need to add if(k >=0){ for(int step=0; step<=k; step++){ int p = a + step*d; // As per constraints, p <=n // But to be safe: if(p >n) break; int r = p%d; L[d][r].push_back(p); } } } // Now, for each d and r, sort and connect consecutive for(int d=1; d<=10; d++){ for(int r=0; r<d; r++){ if(L[d][r].empty()) continue; vector<int> &vec = L[d][r]; sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for(int j=1; j<vec.size(); j++){ uf.union_set(vec[j-1], vec[j]); } } } // Count unique parents int cnt=0; for(int p=1; p<=n; p++) { if(uf.find_set(p) == p) cnt++; } cout<<cnt<<"\n"; } }