結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2015-03-01 16:02:05 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,738 bytes |
コンパイル時間 | 824 ms |
コンパイル使用メモリ | 91,024 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 00:32:18 |
合計ジャッジ時間 | 1,786 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cfloat>#include <map>#include <utility>#include <set>#include <iostream>#include <memory>#include <string>#include <vector>#include <algorithm>#include <functional>#include <sstream>#include <complex>#include <stack>#include <queue>#include <cstring>using namespace std;class UnionFindTree{private:int N;int *rootnum;int *rank;int *unionnum;public:UnionFindTree(int n){/*0からn-1までの要素をunionとしてもつ*/N = n;rootnum = new int[N];rank = new int[N];unionnum = new int[N];for( int i = 0 ; i < N ; i++ ){rootnum[i] = i;rank[i] = 0;unionnum[i] = 1;}}int Find( int j ){if( rootnum[j] == j ){return j;}else{return rootnum[j] = Find(rootnum[j]);}}void Union( int i , int j ){int x = Find(i);int y = Find(j);if( x == y ) return;N--;if( rank[x] < rank[y] ){rootnum[y] = x;unionnum[x] += unionnum[y];}else{rootnum[x] = y;unionnum[y] += unionnum[x];if( rank[x]==rank[y] ) rank[x]++;}}int Num( int j ){/*与えられた要素の入っている集合の要素数を答える*/int x = Find(j);return unionnum[x];}int UnionNum(){/*集合の数を答える*/return N;}~UnionFindTree(){delete rootnum;delete rank;delete unionnum;}};int main(){int N;cin >> N;int Ds[N];int Ws[N];bool ok[N];int tailCnt[N];memset(ok,false,sizeof(ok));memset(tailCnt,0,sizeof(tailCnt));for( int i = 0 ; i < N; i++ ) cin >> Ds[i];for( int i = 0 ; i < N; i++ ) cin >> Ws[i];UnionFindTree uft(N);for( int i = 0 ; i <N; i++ ){int left = (i+Ds[i])%N;int right = (i-Ds[i]+N*1000)%N;//cout << i << "+" << Ds[i]<<": "<< left<< " , ";//cout << i << "-" << Ds[i]<<": "<< right << endl;;uft.Union(left,right);if(left==right){ok[left]=true;}}for( int i = 0; i <N; i++ ){if(ok[i]){ok[uft.Find(i)]=true;}if(Ws[i]==0){tailCnt[uft.Find(i)]++;}}bool yes=true;for( int i = 0 ; i <N; i++ ){if( tailCnt[uft.Find(i)]%2==1 && ok[uft.Find(i)]==false){yes=false;break;}}if( yes ) printf("Yes\n");else printf("No\n");return 0;}