結果

問題 No.74 貯金箱の退屈
ユーザー yaoshimaxyaoshimax
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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){
/*0n-1union*/
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0