oj.uz

Submission #520686

# Submission time Handle Problem Language Result Execution time Memory
520686 2022-01-30T19:46:34 Z chinmayajha Experimental Charges (NOI19_charges) C++17
100 / 100
 196 ms 158392 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long

const int w = 1000050;
int n, m;
char c;
vector<int> parent((int) 1e7), siz((int) 1e7, 1);

int findpar(int x) {
    if(x == parent[x]) return x;
    return parent[x] = findpar(parent[x]);
}

void unite(int x, int y) {
    x = findpar(x);
    y = findpar(y);

    if(x == y) return;
    if(siz[y] > siz[x]) swap(x, y);

    parent[y] = x;
    siz[x] += siz[y];
}

signed main() {
    cin >> n >> m;
    for(int i = 0; i < (int) 1e7; ++i) parent[i] = i;

    int x, y;
    while(m--) {
        cin >> c; cin >> x >> y;
        if(c == 'A') {
            unite(x, y + w);
            unite(x + w, y);
        } else if(c == 'R') {
            unite(x, y);
            unite(x + w, y + w);
        } else {
            int p, q, s;
            p = findpar(x);
            q = findpar(y);
            // r = findpar(x + w);
            s = findpar(y + w);

            if(p == q && p == s) cout << "?";
            else if (p == q) cout << "R";
            else if (p == s) cout << "A";
            else cout << "?";
            cout << "\n";
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 156816 KB Output is correct
2 Correct 64 ms 156848 KB Output is correct
3 Correct 66 ms 156844 KB Output is correct
4 Correct 65 ms 156740 KB Output is correct
5 Correct 67 ms 156780 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 157740 KB Output is correct
2 Correct 172 ms 157724 KB Output is correct
3 Correct 182 ms 157892 KB Output is correct
4 Correct 167 ms 157864 KB Output is correct
5 Correct 155 ms 157756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 158372 KB Output is correct
2 Correct 196 ms 158108 KB Output is correct
3 Correct 191 ms 158140 KB Output is correct
4 Correct 173 ms 158152 KB Output is correct
5 Correct 182 ms 158268 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 158200 KB Output is correct
2 Correct 185 ms 158392 KB Output is correct
3 Correct 159 ms 158104 KB Output is correct
4 Correct 169 ms 158240 KB Output is correct
5 Correct 160 ms 158140 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 156816 KB Output is correct
2 Correct 64 ms 156848 KB Output is correct
3 Correct 66 ms 156844 KB Output is correct
4 Correct 65 ms 156740 KB Output is correct
5 Correct 67 ms 156780 KB Output is correct
6 Correct 67 ms 156880 KB Output is correct
7 Correct 67 ms 156868 KB Output is correct
8 Correct 67 ms 156804 KB Output is correct
9 Correct 66 ms 156748 KB Output is correct
10 Correct 66 ms 156736 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 156816 KB Output is correct
2 Correct 64 ms 156848 KB Output is correct
3 Correct 66 ms 156844 KB Output is correct
4 Correct 65 ms 156740 KB Output is correct
5 Correct 67 ms 156780 KB Output is correct
6 Correct 160 ms 157740 KB Output is correct
7 Correct 172 ms 157724 KB Output is correct
8 Correct 182 ms 157892 KB Output is correct
9 Correct 167 ms 157864 KB Output is correct
10 Correct 155 ms 157756 KB Output is correct
11 Correct 182 ms 158372 KB Output is correct
12 Correct 196 ms 158108 KB Output is correct
13 Correct 191 ms 158140 KB Output is correct
14 Correct 173 ms 158152 KB Output is correct
15 Correct 182 ms 158268 KB Output is correct
16 Correct 174 ms 158200 KB Output is correct
17 Correct 185 ms 158392 KB Output is correct
18 Correct 159 ms 158104 KB Output is correct
19 Correct 169 ms 158240 KB Output is correct
20 Correct 160 ms 158140 KB Output is correct
21 Correct 67 ms 156880 KB Output is correct
22 Correct 67 ms 156868 KB Output is correct
23 Correct 67 ms 156804 KB Output is correct
24 Correct 66 ms 156748 KB Output is correct
25 Correct 66 ms 156736 KB Output is correct
26 Correct 186 ms 158248 KB Output is correct
27 Correct 182 ms 158136 KB Output is correct
28 Correct 155 ms 158052 KB Output is correct
29 Correct 151 ms 158020 KB Output is correct
30 Correct 163 ms 158252 KB Output is correct