제출 #227882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
227882		Vimmer	Zamjena (COCI18_zamjena)	C++14	70 / 70	116 ms	10492 KiB

zamjena

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14