ID Unique#11853

ID Unique (Corrigé)

Auteur du Problème:

Hasan Saleh (MathModel)

Préparé par:

Hasan Saleh (MathModel)

Éditeur:

Hasan Saleh (MathModel)

Solution Nous devons vérifier que la relation est UN-DEUX-TROIS, c'est-à-dire que chaque chaîne est utilisée pour un seul entier et que chaque entier est utilisé pour une seule chaîne, ce qui peut être fait avec des ensembles et des cartes.

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


void solve() {
    int n;cin>>n;
    // chaque chaîne est utilisée pour un seul objet
    // et l'ID est utilisé pour une seule chaîne différente
    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="OUI";
    for(auto i:a){
        if(i.second.size()>1){
            ans="ERREUR";
        }
    }
    for(auto i:b){
        if(i.second.size()>1){
            ans="ERREUR";
        }
    }
    cout<<ans<<"\n";
}

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

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

Difficulté \mathcal{O}(n \log n)