Submission #863077

#	Time	Username	Problem	Language	Result	Execution time	Memory
863077		LinkedArray	Zamjena (COCI18_zamjena)	C++17	70 / 70	128 ms	44244 KiB

zamjena

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5;

string numA[MAXN], numB[MAXN];

map<string, vector<string>> sol;
set<string> isKnown;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int i, n, numSolutions;
    string top;

    cin >> n;
    for(i = 0; i < n; i++){
        cin >> numA[i];
    }
    for(i = 0; i < n; i++){
        cin >> numB[i];

        if(numA[i] != numB[i]){
            sol[ numA[i] ].push_back( numB[i] ); // adding all the possible solutions for these elements
            sol[ numB[i] ].push_back( numA[i] );
        }
    }

    for(auto elem : sol){
        if(isKnown.find(elem.first) == isKnown.end()) { // if we don't know this element
            numSolutions = 0;

            queue<string> q;

            q.push(elem.first);
            isKnown.insert(elem.first);

            if('0' <= elem.first[0] && elem.first[0] <= '9') {
                ++numSolutions;
            }

            while(!q.empty()){ // We go through each solutions and check if we reached a number ( => we have an answer) and we count those numbers (in the end the number)
                               // should be <= 1, otherwise the num would be > 1 => we have more than one solution => not possible => we output "NE" and terminate the program
                top = q.front();
                q.pop();

                for(auto e : sol[top]){
                    if(isKnown.find(e) == isKnown.end()){ // If we don't know its value
                        isKnown.insert(e);

                        if('0' <= e[0] && e[0] <= '9') { // if we met a number
                            ++numSolutions; // we count it as a solution
                        }

                        q.push(e);
                    }
                }
            }

            if(numSolutions > 1){ // if we have more than 1 solutions
                cout << "NE\n";
                return 0;
            }
        }
    }
    cout << "DA\n";
    return 0;
}

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