oj.uz

Submission #197859

# Submission time Handle Problem Language Result Execution time Memory
197859 2020-01-23T17:36:27 Z Osama_Alkhodairy Zamjena (COCI18_zamjena) C++17
70 / 70
 314 ms 8904 KB 
#include <bits/stdc++.h>
using namespace std;
#define finish(x){cout << x << endl; exit(0);}
#define ll long long

int n;
vector <string> a, b;
map <string, string> p;

bool num(string &x){
    return '0' <= x[0] && x[0] <= '9';
}
string find(string x){
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}
void merge(string a, string b){
    a = find(a);
    b = find(b);
    p[a] = b;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    for(auto &i : a) cin >> i;
    b.resize(n);
    for(auto &i : b) cin >> i;
    for(int i = 0 ; i < n ; i++){
        p[a[i]] = a[i];
        p[b[i]] = b[i];
    }
    for(int i = 0 ; i < n ; i++){
        merge(a[i], b[i]);
    }
    set <string> nums;
    for(int i = 0 ; i < n ; i++){
        if(num(a[i])) nums.insert(a[i]);
        if(num(b[i])) nums.insert(b[i]);
    }
    set <string> all;
    for(auto &i : nums) all.insert(find(i));
    if(all.size() != nums.size()) cout << "NE\n";
    else cout << "DA\n";
}

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 256 KB Output is correct
5 Correct 2 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 10 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 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 3 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 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 10 ms 760 KB Output is correct
4 Correct 12 ms 888 KB Output is correct
5 Correct 10 ms 888 KB Output is correct
6 Correct 11 ms 760 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1684 KB Output is correct
2 Correct 72 ms 3212 KB Output is correct
3 Correct 147 ms 5044 KB Output is correct
4 Correct 173 ms 6268 KB Output is correct
5 Correct 314 ms 8904 KB Output is correct
6 Correct 230 ms 6324 KB Output is correct