oj.uz

Submission #398123

# Submission time Handle Problem Language Result Execution time Memory
398123 2021-05-03T18:00:20 Z palilo Zamjena (COCI18_zamjena) C++17
70 / 70
 33 ms 4568 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;

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

    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)
        dsu.merge(a[i], b[i]);

    vector<bool> check(hash_val);
    for (int i = 1; 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 268 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 #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 216 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 460 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Correct 11 ms 1476 KB Output is correct
3 Correct 18 ms 2636 KB Output is correct
4 Correct 22 ms 2932 KB Output is correct
5 Correct 33 ms 4568 KB Output is correct
6 Correct 25 ms 2624 KB Output is correct