oj.uz

Submission #651698

# Submission time Handle Problem Language Result Execution time Memory
651698 2022-10-19T20:03:58 Z ktkerem Zamjena (COCI18_zamjena) C++17
70 / 70
 264 ms 12328 KB 
#include<bits/stdc++.h>
typedef long long ll;
typedef std::pair<ll , ll> llll;
typedef std::string str;
std::vector<ll> ar;
std::map<str , str> par , plt;
std::map<str , ll> siz;
str fin(str crt){
    if(crt == par[crt]){
        return crt;
    }
    return par[crt] = fin(par[crt]);
}
void mrg(str x , str y){
    x = fin(x);y = fin(y);
    if(x != y){
        if(siz[x] < siz[y]){
            swap(x , y);
        }
        par[y] = x;
        siz[x] += siz[y];
    }
}
ll n;
void solve(){
    std::cin >> n;
    str h[n][2];
    for(ll i = 0;n>i;i++){
        std::cin >> h[i][0];
        par[h[i][0]] = h[i][0];
        siz[h[i][0]] = 1;
    }
    for(ll i = 0;n>i;i++){
        std::cin >> h[i][1];
        par[h[i][1]] = h[i][1];
        siz[h[i][1]] = 1;
    }
    for(ll i = 0;n>i;i++){
        mrg(h[i][1] , h[i][0]);
    }
    for(ll i = 0;n>i;i++){
        if(h[i][0][0] >= '0' && h[i][0][0] <= '9'){
            str o = fin(h[i][0]);
            if(plt[o].size() == 0){
                plt[o] = h[i][0];
            }
            else if(plt[o] != h[i][0]){
                std::cout << "NE\n";
                return;
            }
        }
        if(h[i][1][0] >= '0' && h[i][1][0] <= '9'){
            str o = fin(h[i][1]);
            if(plt[o].size() == 0){
                plt[o] = h[i][1];
            }
            else if(plt[o] != h[i][1]){
                std::cout << "NE\n";
                return;
            }
        }
    }
    std::cout << "DA\n";
}

int main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t = 1;
    //std::cin >> t;
    while(t--){
        solve();
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 232 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 12 ms 852 KB Output is correct
4 Correct 9 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 8 ms 852 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2128 KB Output is correct
2 Correct 61 ms 4292 KB Output is correct
3 Correct 116 ms 6968 KB Output is correct
4 Correct 172 ms 8120 KB Output is correct
5 Correct 264 ms 12328 KB Output is correct
6 Correct 167 ms 7760 KB Output is correct