Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <set>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- void get_len(int v, vector <int>& parent, vector <int>& len, vector <int> &answer) {
- if (parent[v] == v) {
- answer.push_back(len[v]);
- return;
- }
- get_len(parent[v], parent, len, answer);
- }
- int get_parent(int v, vector <int>& parent, int &father, vector <int> &sz) {
- if (parent[v] == v) {
- father = v;
- return v;
- }
- return get_parent(parent[v], parent, father, sz);
- parent[v] = father;
- }
- void unite(int fr, int to, int we, vector <int>& parent, vector <int>& len, vector <int> &sz) {
- int fath_1 = -1;
- int dad_1 = get_parent(fr, parent, fath_1, sz);
- int fath_2 = -2;
- int dad_2 = get_parent(to, parent, fath_2, sz);
- int ans;
- if (dad_1 == dad_2) {
- len[dad_1] += we;
- }
- else if (sz[dad_1] <= sz[dad_2]) {
- parent[dad_1] = dad_2;
- len[dad_2] += len[dad_1];
- len[dad_2] += we;
- sz[dad_2] += sz[dad_1];
- }
- else {
- parent[dad_2] = dad_1;
- len[dad_1] += len[dad_2];
- len[dad_1] += we;
- sz[dad_1] += sz[dad_2];
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n, m;
- cin >> n >> m;
- vector <int> parent(n + 1);
- for (int i = 1; i < n + 1; ++i) {
- parent[i] = i;
- }
- vector <int> sz(n + 1, 1); //размеры компонент связности -- сколько вершин
- vector <int> len(n + 1, 0); //суммарные длины рёбер каждой компоненты связности -- хранятся в родителях
- vector <int> answer;
- for (int i = 0; i < m; ++i) {
- int oper;
- cin >> oper;
- if (oper == 2) {
- int v;
- cin >> v;
- get_len(v, parent, len, answer);
- }
- else if (oper == 1) {
- int fr, to, we;//from,to,weight
- cin >> fr >> to >> we;
- unite(fr, to, we, parent, len, sz);
- }
- /*cout << "parent\n";
- for (auto x : parent) cout << x << ' ';
- cout << '\n';
- cout << "len\n";
- for (auto x : len) {
- cout << x << ' ';
- }cout << '\n';
- cout << "size\n";
- for (auto x : sz) cout << x << ' ';
- cout << '\n';
- cout << '\n';*/
- }
- for (auto x : answer) cout << x << '\n';
- }
Add Comment
Please, Sign In to add comment