Unique ID#11853

Unique ID (Анализа решења)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution We need to check if the relationship is ONE-TO-ONE , i.e. each string appears is used for a single integer and each integer is exactly used for one string , this can be done with sets and maps.

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


void solve() {
    int n;cin>>n;
    //each string is used for one thing only
    //and ID is used for single distinct string
    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="YES";
    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++

Complexity $O (n lo g n)$ \mathcal{O}(n \log n)