oj.uz

Submission #1008073

# Submission time Handle Problem Language Result Execution time Memory
1008073 2024-06-26T07:24:40 Z vicvic Zamjena (COCI18_zamjena) C++11
70 / 70
 51 ms 6504 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1116 KB Output is correct
2 Correct 12 ms 2140 KB Output is correct
3 Correct 17 ms 3512 KB Output is correct
4 Correct 24 ms 4020 KB Output is correct
5 Correct 51 ms 6504 KB Output is correct
6 Correct 31 ms 2908 KB Output is correct