Submission #1008073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008073		vicvic	Zamjena (COCI18_zamjena)	C++11	70 / 70	51 ms	6504 KiB

zamjena

#include <iostream>
#include <unordered_map>
#include <set>
#include <cstring>
#include <string>
using namespace std;
unordered_map <int, int> umap;
unordered_map <string, int> found;
int v[50005], v1[50005], n, cnt=1006;
int transform_nr (string s)
{
    if (!isdigit (s[0]))
    {
        if (found[s])
        {
            return found[s];
        }
        else
        {
            found[s]=++cnt;
            return found[s];
        }
    }
    else
    {
        int nr=0;
        for (int i=0; s[i]; i++)
        {
            nr=nr*10+s[i]-'0';
        }
        return nr;
    }
}
int main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        string s;
        cin >> s;
        v[i]=transform_nr (s);
    }
    for (int i=1; i<=n; i++)
    {
        string s;
        cin >> s;
        v1[i]=transform_nr (s);
    }
    for (int i=1; i<=n; i++)
    {
        if (v[i]<=1000 && v1[i]<=1000)
        {
            if (v[i]!=v1[i])
            {
                cout << "NE";
                return 0;
            }
        }
        if (v[i]>1000 && v1[i]<=1000)
        {
            if (umap[v[i]] && umap[v[i]]!=v1[i])
            {
                cout << "NE";
                return 0;
            }
            umap[v[i]]=v1[i];
        }
        if (v[i]<=1000 && v1[i]>1000)
        {
            if (umap[v1[i]] && umap[v1[i]]!=v[i])
            {
                cout << "NE";
                return 0;
            }
            umap[v1[i]]=v[i];
        }
        if (v[i]>1000 && v1[i]>1000)
        {
            if (!umap[v[i]] && !umap[v1[i]])
            {
                continue;
            }
            if (umap[v[i]] && umap[v1[i]] && umap[v[i]]!=umap[v1[i]])
            {
                cout << "NE";
                return 0;
            }
            else if (!umap[v[i]])
            {
                umap[v[i]]=umap[v1[i]];
            }
            else if (!umap[v1[i]])
            {
                umap[v1[i]]=umap[v[i]];
            }
        }
    }
    bool edited=1;
    while (edited)
    {
        edited=0;
        for (int i=1; i<=n; i++)
        {
            if (v[i]>1000 && v1[i]>1000)
            {
                if (!umap[v[i]] && !umap[v1[i]])
                {
                    continue;
                }
                if (umap[v[i]] && umap[v1[i]] && umap[v[i]]!=umap[v1[i]])
                {
                    cout << "NE";
                    return 0;
                }
                else if (!umap[v[i]])
                {
                    umap[v[i]]=umap[v1[i]];
                    edited=1;
                }
                else if (!umap[v1[i]])
                {
                    umap[v1[i]]=umap[v[i]];
                    edited=1;
                }
            }
        }
    }
    cout << "DA";
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14