oj.uz

Submission #642262

# Submission time Handle Problem Language Result Execution time Memory
642262 2022-09-19T05:57:59 Z 1zaid1 Inside information (BOI21_servers) C++17
0 / 100
 32 ms 1592 KB 
#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

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 1540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 1540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1548 KB Output isn't correct
2 Halted 0 ms 0 KB -