oj.uz

Submission #81719

# Submission time Handle Problem Language Result Execution time Memory
81719 2018-10-26T10:31:20 Z Mouhanad_Hafez Zamjena (COCI18_zamjena) C++11
70 / 70
 984 ms 63916 KB 
#include<bits/stdc++.h>
using namespace std;
unordered_map <string, int> mp;
unordered_map <string, vector <string> > v;
string arr1[100007],arr2[100007];
bool ch (string s)
{
    if ((int)(s[0]-'0') <= 10)return 1;
    return 0;
}
int toint (string s)
{
    int t=1,sum=0;
    for (int i=s.size()-1; i>=0; i--)
    {
        sum+=(s[i]-'0')*t;
        t*=10;
    }
    return sum;
}
void dfs (string u, int x)
{
    mp[u] = x;
    for (auto w : v[u])
        if (!mp.count (w))
            dfs (w, x);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)cin>>arr1[i];
    for (int i = 0; i < n; i++)cin>>arr2[i];
    for (int j = 1; j <= 10; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if (ch (arr1[i]))
            {
                if (ch (arr2[i]))
                {
                    if (arr1[i] != arr2[i])
                    {
                        cout << "NE" ;
                        return 0;
                    }
                }
                else
                {
                    int x = toint (arr1[i]);
                    if (!mp.count (arr2[i]))
                    {
                        dfs (arr2[i], x);
                    }
                    if (!mp.count (arr2[i])||mp[arr2[i]] == x)
                        mp[arr2[i]] = x;
                    else
                    {
                        cout << "NE" ;
                        return 0;
                    }
                }
            }
            else
            {
                if (ch (arr2[i]))
                {
                    int x = toint (arr2[i]);
                    if (!mp.count (arr1[i]))
                    {
                        dfs (arr1[i], x);
                    }
                    if (!mp.count (arr1[i])||mp[arr1[i]] == x)
                        mp[arr1[i]] = x;
                    else
                    {
                        cout << "NE" ;
                        return 0;
                    }
                }
                else
                {
                    if (mp.count (arr1[i]))
                    {
                        if (mp.count (arr2[i]))
                        {
                            if (mp[arr1[i]] != mp[arr2[i]])
                            {
                                cout << "NE" ;
                                return 0;
                            }
                        }
                        else
                        {
                            mp[arr2[i]] = mp[arr1[i]];
                        }
                    }
                    else if (mp.count (arr2[i]))
                    {
                        mp[arr1[i]] = mp[arr2[i]];
                    }
                    v[arr1[i]].push_back (arr2[i]);
                    v[arr2[i]].push_back (arr1[i]);
                }
            }
        }
    }
    cout << "DA" ;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6652 KB Output is correct
2 Correct 7 ms 6768 KB Output is correct
3 Correct 7 ms 6768 KB Output is correct
4 Correct 8 ms 6768 KB Output is correct
5 Correct 7 ms 6768 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6768 KB Output is correct
2 Correct 7 ms 6792 KB Output is correct
3 Correct 7 ms 6792 KB Output is correct
4 Correct 7 ms 6840 KB Output is correct
5 Correct 7 ms 6840 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6892 KB Output is correct
2 Correct 7 ms 6892 KB Output is correct
3 Correct 14 ms 6892 KB Output is correct
4 Correct 10 ms 6892 KB Output is correct
5 Correct 8 ms 6892 KB Output is correct
6 Correct 8 ms 6892 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7932 KB Output is correct
2 Correct 13 ms 7932 KB Output is correct
3 Correct 11 ms 7932 KB Output is correct
4 Correct 11 ms 7932 KB Output is correct
5 Correct 34 ms 9344 KB Output is correct
6 Correct 11 ms 9344 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9344 KB Output is correct
2 Correct 228 ms 25852 KB Output is correct
3 Correct 99 ms 25852 KB Output is correct
4 Correct 60 ms 25852 KB Output is correct
5 Correct 984 ms 63916 KB Output is correct
6 Correct 634 ms 63916 KB Output is correct