Submission #642262

#	Time	Username	Problem	Language	Result	Execution time	Memory
642262		1zaid1	Inside information (BOI21_servers)	C++17	0 / 100	32 ms	1592 KiB

servers

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n';

const int M = 2e5+5;
int p[M], sz[M];

int find(int x) {
    return (p[x]==x?x:find(p[x]));
}

void uni(int a, int b) {
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, k;
    cin >> n >> k;
    int q = n+k-1;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= n; i++) sz[i] = 1;
    while (q--) {
        char c;
        cin >> c;

        if (c == 'S') {
            int a, b;
            cin >> a >> b;
            uni(find(a), find(b));
        } if (c == 'Q') {
            int a, b;
            cin >> a >> b;
            cout << (find(a) == find(b)?"yes":"no") << endl;
        } if (c == 'C') {
            int x;
            cin >> x;

            cout << sz[find(x)] << endl;
        }
    }

    return 0;
}

/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6

a b c
ab ab c
abc ab abc
*/

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5