oj.uz

Submission #1108319

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

struct DSU {
    vector<int> size, link, charge;
    vector<vector<int>> adj;
    DSU(int sz) {
        size.resize(sz+1, 1);
        link.resize(sz+1);
        charge.resize(sz+1, 1);
        adj.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, bool res) {
        if (same(a, b)) return;
        if (size[a] < size[b]) swap(a, b);
        if ((charge[a] == charge[b] && res) || (charge[a] != charge[b] && !res)) {
            a = find(a);
            b = find(b);
            dfs(b, b);
        }
        else {
            a = find(a);
            b = find(b);
        }
        size[a] += size[b];
        link[b] = a;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    void dfs(int cur, int p) {
        charge[cur] = 1-charge[cur];
        for (auto e : adj[cur]) {
            if (e != p) dfs(e, cur);
        }
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    // freopen("in.txt", "r", stdin);
    int n, q;
    cin >> n >> q;
    DSU d(n);
    while (q--) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'R') {
            if (d.same(a, b)) continue;
            else d.unite(a, b, 0);
        }
        else if (c == 'A') {
            if (d.same(a, b)) continue;
            else d.unite(a, b, 1);
        }
        else {
            if (d.same(a, b)) {
                if (d.charge[a] == d.charge[b]) cout << "R\n";
                else 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 0 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 504 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5580 KB Output is correct
2 Correct 19 ms 5836 KB Output is correct
3 Correct 16 ms 5068 KB Output is correct
4 Correct 18 ms 5660 KB Output is correct
5 Correct 19 ms 5836 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5580 KB Output is correct
2 Execution timed out 1067 ms 5380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 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 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 592 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 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 504 KB Output is correct
6 Correct 17 ms 5580 KB Output is correct
7 Correct 19 ms 5836 KB Output is correct
8 Correct 16 ms 5068 KB Output is correct
9 Correct 18 ms 5660 KB Output is correct
10 Correct 19 ms 5836 KB Output is correct
11 Correct 22 ms 5580 KB Output is correct
12 Execution timed out 1067 ms 5380 KB Time limit exceeded
13 Halted 0 ms 0 KB -