結果
問題 | No.2346 Replace!! |
ユーザー |
|
提出日時 | 2023-06-10 00:08:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 1,281 bytes |
コンパイル時間 | 871 ms |
コンパイル使用メモリ | 72,660 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-01-02 06:34:24 |
合計ジャッジ時間 | 5,319 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 73 |
ソースコード
#include<iostream> #include<vector> using namespace std; int N,A[5000],B[5000]; bool vis[5000]; bool loop[5000]; int inv[5000],deg[5000]; bool check(vector<int>L) { while(true) { for(int i=0;i<L.size();i++) { inv[L[i]]=i; deg[i]=0; } for(int i=0;i<L.size();i++) { deg[inv[B[L[i]]]]++; } bool fn=false; int use=-1; for(int i=0;i<L.size();i++) { if(B[L[i]]!=L[(i+1)%L.size()]) { fn=true; if(deg[(i+1)%L.size()]==0)use=(i+1)%L.size(); } } if(!fn)return true; if(use==-1)return false; L.erase(L.begin()+use); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin>>T; for(;T--;) { cin>>N; for(int i=0;i<N;i++)cin>>A[i],A[i]--; for(int i=0;i<N;i++)cin>>B[i],B[i]--; for(int i=0;i<N;i++)loop[i]=false; bool ok=true; vector<vector<int> >loops; for(int i=0;i<N;i++) { int u=A[i]; for(int j=0;j<N;j++)vis[j]=false; while(!vis[u]) { vis[u]=true; u=A[u]; } if(!vis[B[i]])ok=false; if(u==A[i]&&!loop[u]) { loops.push_back(vector<int>()); while(!loop[u]) { loops.back().push_back(u); loop[u]=true; u=A[u]; } } } if(ok) { for(vector<int>L:loops) { if(!check(L))ok=false; } } cout<<(ok?"Yes\n":"No\n"); } }