oj.uz

Submission #115175

# Submission time Handle Problem Language Result Execution time Memory
115175 2019-06-05T20:55:56 Z izanbf Zamjena (COCI18_zamjena) C++14
70 / 70
 30 ms 4968 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << ", "
template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){ \
 if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;}
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef unsigned int uint;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unsigned char uchar;
struct secure_hash {
 static uint64_t splitmix64(uint64_t x) {
  x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
 size_t operator()(uint64_t x) const {
  static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } };
template<typename T> using V = vector<T>;
template<typename T, typename U> using umap = unordered_map<T,U>;
template<typename T> using uset = unordered_set<T>;
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using max_heap = priority_queue<T>;

int parent[300000], size[300000], value[300000];
umap<string,int> idt;

bool is_num(string& s)
{
    for (char c : s) {
        if (c < '0' or c > '9') return false;
    }
    return true;
}   

int get_id(string& s)
{
    auto it = idt.find(s);
    if (it == idt.end()) {
        int id = idt.size();
        parent[id] = id;
        size[id] = 1;
        value[id] = (is_num(s) ? stoi(s) : -1);
        idt[s] = id;
        return id;
    }
    return it->second;
}

int ufind(int u)
{
    if (parent[u] != u) parent[u] = ufind(parent[u]);
    return parent[u];
}

bool ujoin(int u, int v)
{
    u = ufind(u), v = ufind(v);
    if (u != v) {
        if (size[u] < size[v]) swap(u, v);
        if (value[u] != -1 and value[v] != -1 and value[u] != value[v]) return false;
        parent[v] = u;
        size[u] += size[v];
        value[u] = max(value[u], value[v]);
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while (cin >> n) {
        V<V<int>> a(2, V<int>(n));
        rep(k,0,2) {
            rep(i,0,n) {
                string s;
                cin >> s;
                a[k][i] = get_id(s);
            }
        }
        bool ok = true;
        rep(i,0,n) {
            if (not ujoin(a[0][i], a[1][i])) {
                ok = false;
                break;
            }
        }
        cout << (ok ? "DA" : "NE") << endl;
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 12 ms 2048 KB Output is correct
3 Correct 18 ms 2944 KB Output is correct
4 Correct 23 ms 3652 KB Output is correct
5 Correct 30 ms 4968 KB Output is correct
6 Correct 24 ms 2876 KB Output is correct