oj.uz

Submission #398116

# Submission time Handle Problem Language Result Execution time Memory
398116 2021-05-03T17:40:30 Z palilo Zamjena (COCI18_zamjena) C++17
42 / 70
 11 ms 1612 KB 
#include <bits/stdc++.h>
using namespace std;

struct disjoint_set {
    vector<int> par;
    disjoint_set(int n) : par(n, -1) {}
    int find(int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;

        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n;
    cin >> n;

    constexpr int mx_val = 1000;
    int hash_val = mx_val;
    unordered_map<string, int> mp;

    auto input = [&]() {
        vector<int> ret(n);
        string s;
        for (auto& x : ret) {
            cin >> s;
            if (isdigit(s[0])) x = stoi(s);
            else {
                if (!mp[s]) mp[s] = hash_val++;
                x = mp[s];
            }
        }
        return ret;
    };

    auto a = input();
    auto b = input();

    disjoint_set dsu(hash_val);

    for (int i = 0; i < n; ++i)
        if (a[i] < mx_val && b[i] < mx_val) {
            if (a[i] != b[i]) return cout << "NE", 0;
        } else
            dsu.merge(a[i], b[i]);

    bitset<mx_val> check;
    for (int i = 0; i < mx_val; ++i) {
        auto root = dsu.find(i);
        if (check[root]) return cout << "NE", 0;
        check[root] = true;
    }
    cout << "DA";
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 844 KB Output is correct
2 Incorrect 11 ms 1612 KB Output isn't correct
3 Halted 0 ms 0 KB -