oj.uz

Submission #227882

# Submission time Handle Problem Language Result Execution time Memory
227882 2020-04-29T06:33:37 Z Vimmer Zamjena (COCI18_zamjena) C++14
70 / 70
 116 ms 10492 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define M ll(1e9 + 7)

using namespace std;

//using namespace __gnu_pbds;

typedef long double ld;

typedef long long ll;

typedef short int si;

//typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


map <string, int> mp;

int id, rk[N], p[N];

string val[N];

void make(string s) {if (mp.find(s) != mp.end()) return; id++; mp[s] = id; val[id] = '-'; p[id] = id; rk[id] = 1;}

int fnd(int x) {if (p[x] != x) p[x] = fnd(p[x]); return p[x];}

void link(int a, int b)
{
    if (a == b) return;

    if (val[a] != val[b] && val[a] != "-" && val[b] != "-") {cout << "NE" << endl; exit(0);}

    if (rk[a] < rk[b]) swap(a, b);

    rk[a] += rk[b];

    p[b] = a;

    if (val[a] == "-") val[a] = val[b];
}

bool gd(string s)
{
    for (int i = 0; i < sz(s); i++)
        if (s[i] - '0' > 9 || s[i] - '0' < 0) return 0;

    return 1;
}

int main()
{
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;

    cin >> n;

    string s[n], t[n];

    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = 0; i < n; i++)
    {
        string str;

        cin >> str;

        t[i] = str;

        bool fr = gd(s[i]), sc = gd(str);

        if (sc && fr)
        {
            if (str == s[i]) continue;

            cout << "NE" << endl;

            exit(0);
        }

        if (!fr && !sc)
        {
            make(str);

            make(s[i]);

            int a = fnd(mp[str]), b = fnd(mp[s[i]]);

            link(a, b);

            continue;
        }

        if (fr && !sc)
        {
            make(str);

            int a = fnd(mp[str]);

            if (val[a] == "-" || val[a] == s[i])
            {
                val[a] = s[i];

                continue;
            }

            cout << "NE" << endl;

            exit(0);
        }

        if (!fr && sc)
        {
            make(s[i]);

            int b = fnd(mp[s[i]]);

            if (val[b] == "-" || val[b] == str)
            {
                val[b] = str;

                continue;
            }

            cout << "NE" << endl;

            exit(0);
        }
    }

    cout << "DA" << endl;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3584 KB Output is correct
2 Correct 7 ms 3584 KB Output is correct
3 Correct 9 ms 3840 KB Output is correct
4 Correct 13 ms 3840 KB Output is correct
5 Correct 11 ms 3840 KB Output is correct
6 Correct 9 ms 3840 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4608 KB Output is correct
2 Correct 34 ms 5880 KB Output is correct
3 Correct 53 ms 7544 KB Output is correct
4 Correct 45 ms 7800 KB Output is correct
5 Correct 116 ms 10492 KB Output is correct
6 Correct 78 ms 8312 KB Output is correct