Унікальний ID#11853

Унікальний ID (Розбір)

Автор проблеми:

Хасан Салех (MathModel)

Підготовлено:

Хасан Салех (MathModel)

Редаговано:

Хасан Салех (MathModel)

Рішення Нам потрібно перевірити, чи відношення є ОДИН-ОДИН, тобто кожен рядок використовується для єдиного цілого числа, і кожне ціле число використовується точно для одного рядка, це можна зробити за допомогою множин і карт.

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

void solve() {
    int n;cin>>n;
    //кожен рядок використовується лише для однієї речі
    //і ID використовується для єдиного різного рядка
    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;
}

Складність \mathcal{O}(n \log n)