oj.uz

Submission #863077

# Submission time Handle Problem Language Result Execution time Memory
863077 2023-10-19T14:48:42 Z LinkedArray Zamjena (COCI18_zamjena) C++17
70 / 70
 128 ms 44244 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31580 KB Output is correct
2 Correct 6 ms 31776 KB Output is correct
3 Correct 7 ms 31772 KB Output is correct
4 Correct 6 ms 31692 KB Output is correct
5 Correct 6 ms 31580 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31576 KB Output is correct
2 Correct 6 ms 31580 KB Output is correct
3 Correct 6 ms 31772 KB Output is correct
4 Correct 6 ms 31580 KB Output is correct
5 Correct 7 ms 31768 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 7 ms 31936 KB Output is correct
3 Correct 9 ms 32092 KB Output is correct
4 Correct 9 ms 32408 KB Output is correct
5 Correct 10 ms 32348 KB Output is correct
6 Correct 9 ms 32088 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33372 KB Output is correct
2 Correct 38 ms 35924 KB Output is correct
3 Correct 34 ms 37204 KB Output is correct
4 Correct 45 ms 38484 KB Output is correct
5 Correct 128 ms 44244 KB Output is correct
6 Correct 71 ms 40272 KB Output is correct