oj.uz

Submission #1108307

# Submission time Handle Problem Language Result Execution time Memory
1108307 2024-11-03T18:16:17 Z toast12 Experimental Charges (NOI19_charges) C++14
18 / 100
 1000 ms 2640 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> size, link;
    vector<bool> added;
    DSU(int sz) {
        size.resize(sz+1);
        link.resize(sz+1);
        added.resize(sz+1);
        iota(link.begin(), link.end(), 0);
    }
    int find(int x) {
        while (x != link[x]) x = link[x];
        return x;
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
    void unite(int a, int b) {
        added[a] = true, added[b] = true;
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        link[b] = a;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    DSU d(n);
    while (q--) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'R') d.unite(a, b);
        else if (c == 'A') d.added[a] = true, d.added[b] = true;
        else if (c == 'Q') {
            if (d.same(a, b)) cout << "R\n";
            else if (d.added[a] && d.added[b]) cout << "A\n";
            else cout << "?\n";
        }
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2164 KB Output is correct
2 Correct 12 ms 2128 KB Output is correct
3 Correct 14 ms 2152 KB Output is correct
4 Correct 14 ms 2128 KB Output is correct
5 Correct 12 ms 2128 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2640 KB Output is correct
2 Execution timed out 1063 ms 2152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 14 ms 2164 KB Output is correct
7 Correct 12 ms 2128 KB Output is correct
8 Correct 14 ms 2152 KB Output is correct
9 Correct 14 ms 2128 KB Output is correct
10 Correct 12 ms 2128 KB Output is correct
11 Correct 15 ms 2640 KB Output is correct
12 Execution timed out 1063 ms 2152 KB Time limit exceeded
13 Halted 0 ms 0 KB -