oj.uz

Submission #124500

# Submission time Handle Problem Language Result Execution time Memory
124500 2019-07-03T12:42:28 Z andreiomd Zamjena (COCI18_zamjena) C++11
70 / 70
 678 ms 8864 KB 
#include <iostream>
#include <cstring>
#include <map>

using namespace std;

const int NMAX = 5e4 + 5, MMAX = 15;

int N, M, n;

char S[MMAX];

bool OK = true;

struct Element
{
    int X;

    char Y[MMAX];
};

Element A[NMAX], B[NMAX];

map < string, int > mp;
map < string, bool > Sel;

inline void Read ()
{
    ios_base :: sync_with_stdio(false);

    cin.tie(NULL);

    cin >> N;

    for(int i = 1; i <= N; ++i)
    {
        cin >> (S + 1);

        M = strlen(S + 1);

        bool Nr = true;

        for(int j = 1; j <= M && Nr; ++j)
            if(!isdigit(S[j]))
                Nr = false;

        if(Nr)
        {
            n = 0;

            for(int j = 1; j <= M; ++j)
                n = n * 10 + (S[j] - '0');

            A[i].X = n;
        }
        else
            for(int j = 1; j <= M; ++j)
                A[i].Y[j] = S[j];
    }

    for(int i = 1; i <= N; ++i)
    {
        cin >> (S + 1);

        M = strlen(S + 1);

        bool Nr = true;

        for(int j = 1; j <= M && Nr; ++j)
            if(!isdigit(S[j]))
                Nr = false;

        if(Nr)
        {
            n = 0;

            for(int j = 1; j <= M; ++j)
                n = n * 10 + (S[j] - '0');

            B[i].X = n;
        }
        else
            for(int j = 1; j <= M; ++j)
                B[i].Y[j] = S[j];
    }

    return;
}

inline void Solve ()
{
    for(int i = 1; i <= N; ++i)
        if(A[i].X && B[i].X)
            if(A[i].X != B[i].X)
            {
                OK = false;

                break;
            }

    if(!OK)
        return;

    bool done = true;

    int op = 0;

    while(done && op * N <= 300000)
    {
        ++op;

        done = false;

        for(int i = 1; i <= N; ++i)
            if(A[i].X && B[i].X)
                continue;
            else
            {
                if(A[i].X)
                {
                    string V;

                    M = strlen(B[i].Y + 1);

                    for(int j = 1; j <= M; ++j)
                        V.push_back(B[i].Y[j]);

                    if(Sel[V])
                    {
                        if(mp[V] != A[i].X)
                        {
                            OK = false;

                            return;
                        }
                        else
                            continue;
                    }
                    else
                    {
                        Sel[V] = true;

                        mp[V] = A[i].X;
                    }
                }
                else
                {
                    if(B[i].X)
                    {
                        string V;

                        M = strlen(A[i].Y + 1);

                        for(int j = 1; j <= M; ++j)
                            V.push_back(A[i].Y[j]);

                        if(Sel[V])
                        {
                            if(mp[V] != B[i].X)
                            {
                                OK = false;

                                return;
                            }
                            else
                                continue;
                        }
                        else
                        {
                            Sel[V] = true;

                            mp[V] = B[i].X;
                        }
                    }
                    else
                    {
                        if(strcmp(A[i].Y + 1, B[i].Y + 1) == 0)
                            continue;

                        string V1, V2;

                        int m1 = (int)strlen(A[i].Y + 1);
                        int m2 = (int)strlen(B[i].Y + 1);

                        for(int j = 1; j <= m1; ++j)
                            V1.push_back(A[i].Y[j]);

                        for(int j = 1; j <= m2; ++j)
                            V2.push_back(B[i].Y[j]);

                        if(Sel[V1] && Sel[V2])
                        {
                            if(mp[V1] != mp[V2])
                            {
                                OK = false;

                                return;
                            }
                            else
                                continue;
                        }
                        else
                        {
                            if(Sel[V1])
                            {
                                Sel[V2] = true;

                                mp[V2] = mp[V1];
                            }
                            else
                            {
                                if(Sel[V2])
                                {
                                    Sel[V1] = true;

                                    mp[V1] = mp[V2];
                                }
                                else
                                    done = true;
                            }
                        }
                    }
                }
            }
    }

    return;
}

int main()
{
    Read();

    Solve();

    if(OK)
        cout << "DA";
    else
        cout << "NE";

    cout << '\n';

    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 19 ms 376 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 158 ms 608 KB Output is correct
3 Correct 7 ms 732 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 235 ms 976 KB Output is correct
6 Correct 5 ms 632 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1272 KB Output is correct
2 Correct 418 ms 3132 KB Output is correct
3 Correct 90 ms 3832 KB Output is correct
4 Correct 70 ms 4984 KB Output is correct
5 Correct 678 ms 8864 KB Output is correct
6 Correct 535 ms 5840 KB Output is correct