Submission #651698

#	Time	Username	Problem	Language	Result	Execution time	Memory
651698		ktkerem	Zamjena (COCI18_zamjena)	C++17	70 / 70	264 ms	12328 KiB

zamjena

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14