Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: C. Experience
- // Contest: Codeforces - ITMO Academy: pilot course - Disjoint Sets Union - Step 1
- // Memory Limit: 64 MB
- // Time Limit: 2000 ms
- // Date / Time: 2022-04-13 18:26:09
- // Author: cosenza
- // всё что ни делается - всё к лучшему
- // check list -> long long, special cases, array size, mod (a*b%p*c%p not a*b*c%p , (a-b+p)%p not a-b )
- //
- // Powered by CP Editor (https://cpeditor.org)
- //Слава Україні, Героям слава 🇺🇦
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2e5 + 7;
- int par[N], sz[N], ex[N];
- int find(int a) {
- return par[a] == a ? a : find(par[a]);
- }
- void unite(int a, int b) {
- if((a = find(a)) == (b = find(b))) {
- return;
- }
- if(sz[a] < sz[b]) {
- swap(a, b);
- }
- par[b] = a;
- sz[a] += sz[b];
- ex[b] -= ex[a];
- }
- int sum(int a) {
- if(par[a] == a) {
- return ex[a];
- } else {
- return ex[a] + sum(par[a]);
- }
- }
- void add(int a, int x) {
- a = find(a);
- ex[a] += x;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- for(int i = 0; i < N; i++) {
- par[i] = i;
- sz[i] = 1;
- }
- int n, q;
- cin >> n >> q;
- while(q--) {
- string s;
- cin >> s;
- if(s == "add") {
- int x, y;
- cin >> x >> y;
- add(x, y);
- } else if(s == "join") {
- int x, y;
- cin >> x >> y;
- unite(x, y);
- } else {
- int x;
- cin >> x;
- cout << sum(x) << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement