Автор проблеми: | Хасан Салех (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)