Korotkodul

Problem B. Вес компоненты

Oct 6th, 2021 (edited)
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.46 KB | None | 0 0
  1. #include <set>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7.  
  8. void get_len(int v, vector <int>& parent, vector <int>& len, vector <int> &answer) {
  9.     if (parent[v] == v) {
  10.         answer.push_back(len[v]);
  11.         return;
  12.     }
  13.     get_len(parent[v], parent, len, answer);
  14. }
  15.  
  16. int get_parent(int v, vector <int>& parent, int &father, vector <int> &sz) {
  17.     if (parent[v] == v) {
  18.         father = v;
  19.         return v;
  20.     }
  21.     return get_parent(parent[v], parent, father, sz);
  22.     parent[v] = father;
  23. }
  24.  
  25. void unite(int fr, int to, int we, vector <int>& parent, vector <int>& len, vector <int> &sz) {
  26.     int fath_1 = -1;
  27.     int dad_1 = get_parent(fr, parent, fath_1, sz);
  28.     int fath_2 = -2;
  29.     int dad_2 = get_parent(to, parent, fath_2, sz);
  30.     int ans;
  31.     if (dad_1 == dad_2) {
  32.         len[dad_1] += we;
  33.     }
  34.     else if (sz[dad_1] <= sz[dad_2]) {
  35.         parent[dad_1] = dad_2;
  36.         len[dad_2] += len[dad_1];
  37.         len[dad_2] += we;
  38.         sz[dad_2] += sz[dad_1];
  39.     }
  40.     else {
  41.         parent[dad_2] = dad_1;
  42.         len[dad_1] += len[dad_2];
  43.         len[dad_1] += we;
  44.         sz[dad_1] += sz[dad_2];
  45.     }
  46. }
  47.  
  48.  
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(0);
  53.     int n, m;
  54.     cin >> n >> m;
  55.     vector <int> parent(n + 1);
  56.     for (int i = 1; i < n + 1; ++i) {
  57.         parent[i] = i;
  58.     }
  59.     vector <int> sz(n + 1, 1); //размеры компонент связности -- сколько вершин
  60.     vector <int> len(n + 1, 0); //суммарные длины рёбер каждой компоненты связности -- хранятся в родителях
  61.     vector <int> answer;
  62.     for (int i = 0; i < m; ++i) {
  63.         int oper;
  64.         cin >> oper;
  65.         if (oper == 2) {
  66.             int v;
  67.             cin >> v;
  68.             get_len(v, parent, len, answer);
  69.         }
  70.         else if (oper == 1) {
  71.             int fr, to, we;//from,to,weight
  72.             cin >> fr >> to >> we;
  73.             unite(fr, to, we, parent, len, sz);
  74.         }
  75.         /*cout << "parent\n";
  76.         for (auto x : parent) cout << x << ' ';
  77.         cout << '\n';
  78.         cout << "len\n";
  79.         for (auto x : len) {
  80.             cout << x << ' ';
  81.         }cout << '\n';
  82.         cout << "size\n";
  83.         for (auto x : sz) cout << x << ' ';
  84.         cout << '\n';
  85.         cout << '\n';*/
  86.     }
  87.     for (auto x : answer) cout << x << '\n';
  88. }
  89.  
  90.  
Add Comment
Please, Sign In to add comment