oj.uz

Submission #115456

# Submission time Handle Problem Language Result Execution time Memory
115456 2019-06-07T14:53:08 Z Vlatko Zamjena (COCI18_zamjena) C++14
70 / 70
 108 ms 5368 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;



struct DSU {
    int n;
    vector<int> p, rank;
    DSU(int _n) {
        n = _n;
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        rank.assign(n, 0);
    }
    inline int get(int x) {
        return p[x] == x ? x : (p[x] = get(p[x]));
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (rank[x] > rank[y]) {
            p[y] = x;
        } else {
            p[x] = y;
            if (rank[x] == rank[y]) {
                ++rank[y];
            }
        }
        return true;
    }
};

const int maxn = 50005;
const int unset = -2*maxn;

int n;
int a[maxn], b[maxn];

int variables;
int value[maxn];
map<string, int> vid;
DSU dsu(maxn);

int getid(string& s) {
    if (vid.count(s)) {
        return vid[s];
    } else {
        return vid[s] = variables++;
    }
}

void read(int arr[maxn]) {
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        if (s[0] >= 'a' && s[0] <= 'z') {
            arr[i] = getid(s);
        } else {
            arr[i] = -stoi(s);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    variables = 0;
    read(a);
    read(b);
    fill(value, value+maxn, unset);

    for (int i = 0; i < n; ++i) {
        if (a[i] >= 0) {
            a[i] = dsu.get(a[i]);
        }
        if (b[i] >= 0) {
            b[i] = dsu.get(b[i]);
        }
        if (a[i] < 0 && b[i] < 0) {
            if (a[i] != b[i]) {
                cout << "NE\n";
                return 0;
            }
        } else if (a[i] >= 0 && b[i] >= 0) {
            if (value[a[i]] == unset && value[b[i]] == unset) {
                dsu.unite(a[i], b[i]);
            } else if (value[a[i]] == unset && value[b[i]] != unset) {
                value[a[i]] = value[b[i]];
            } else if (value[a[i]] != unset && value[b[i]] == unset) {
                value[b[i]] = value[a[i]];
            } else if (value[a[i]] != value[b[i]]) {
                cout << "NE\n";
                return 0;
            }
        } else {
            if (a[i] < 0) {
                swap(a[i], b[i]);
            }
            // a[i] is variable, b[i] is constant
            if (value[a[i]] == unset) {
                value[a[i]] = b[i];
            } else if (value[a[i]] != b[i]) {
                cout << "NE\n";
                return 0;
            }
        }
    }

    cout << "DA\n";

}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 6 ms 1280 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1536 KB Output is correct
2 Correct 25 ms 2228 KB Output is correct
3 Correct 48 ms 3320 KB Output is correct
4 Correct 51 ms 3576 KB Output is correct
5 Correct 108 ms 5368 KB Output is correct
6 Correct 75 ms 3320 KB Output is correct