結果
問題 | No.2148 ひとりUNO |
ユーザー |
![]() |
提出日時 | 2022-12-03 14:51:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,479 bytes |
コンパイル時間 | 2,296 ms |
コンパイル使用メモリ | 219,564 KB |
最終ジャッジ日時 | 2025-02-09 04:46:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } //INSERT ABOVE HERE signed solve(){ int n; cin>>n; map<string, set<int>> mp; for(int i=0;i<n;i++){ string c; int d; cin>>c>>d; mp[c].emplace(d); } vector<string> ks; for(auto&[k,v]:mp) ks.emplace_back(k); sort(ks.begin(),ks.end()); if(ks.size()==1){ cout<<"YES"<<newl; return 0; } int ok=0; do{ int ng=0; auto cur=mp[ks[0]]; for(int i=1;i<(int)ks.size();i++){ auto nxt=mp[ks[i]]; set<int> intersection; for(int l:cur) if(nxt.count(l)) intersection.emplace(l); if(intersection.size()==0){ ng=1; break; } if(intersection.size()==1){ if(nxt.size()!=1){ nxt.erase(*intersection.begin()); } cur=nxt; continue; } cur=nxt; } if(!ng) ok=1; }while(next_permutation(ks.begin(),ks.end())); cout<<(ok?"YES":"NO")<<newl; return 0; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); int t; cin>>t; while(t--) solve(); return 0; }