ID Único#11853
Iniciar sesión

ID Único (Editorial)

Autor del Problema:

Hasan Saleh (MathModel)

Preparado por:

Hasan Saleh (MathModel)

Editado por:

Hasan Saleh (MathModel)

Solución Necesitamos verificar si la relación es UNO A UNO, es decir, cada cadena se usa para un solo entero y cada entero se usa exactamente para una cadena, esto se puede hacer con conjuntos y mapas.

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

void solve() {
    int n;cin>>n;
    //cada cadena se usa para una sola cosa
    //y el ID se usa para una única cadena distinta
    map<string,set<int>>a;
    map<int,set<string>>b;
    while(n--){
        string s;cin>>s;
        int x;cin>>x;
        a[s].insert(x);
        b[x].insert(s);
    }
    string ans="SÍ";
    for(auto i:a){
        if(i.second.size()>1){
            ans="NO";
        }
    }
    for(auto i:b){
        if(i.second.size()>1){
            ans="NO";
        }
    }
    cout<<ans<<"\n";
}

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

    int T;cin>>T;
    while (T--) solve();
    return 0;
}
C++

Complejidad \mathcal{O}(n \log n)