結果

問題 No.74 貯金箱の退屈
ユーザー EmKjpEmKjp
提出日時 2015-03-25 07:59:07
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,188 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 88,180 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-29 00:46:58
合計ジャッジ時間 1,828 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>
using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
typedef vector<int> VI;
typedef vector<VI> VVI;
struct QuickFindWeighted {
vector<int> to_main;
vector<vector<int> > groups;
QuickFindWeighted(int n) : to_main(n), groups(n) {
FOR(i,n) to_main[i] = i ;
FOR(i,n) groups[i].push_back(i);
}
void merge(int large, int small){
FOR(i,SZ(groups[small])) {
int e = groups[small][i];
groups[large].push_back(e);
to_main[e] = large;
}
groups[small].clear();
}
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if(x == y) return false;
if(size(x) >= size(y)) merge(x, y);
else merge(y, x);
return x != y;
}
bool is_sameSet(int x, int y) { return root(x) == root(y); }
int root(int x) { return to_main[x]; }
int size(int x) { return groups[x].size(); }
};
int main()
{
int N;
cin>>N;
VI D(N);
VI W(N);
FOR(i,N) cin>>D[i];
FOR(i,N) cin>>W[i];
VI canFlip(N), Flip1(N);
QuickFindWeighted u(N);
FOR(i,N){
int a = (i + D[i]) % N;
int b = (i - D[i] % N + N) % N;
canFlip[a] = canFlip[b] = true;
if(a != b) {
u.unionSet(a,b);
}else{
Flip1[a] = true;
}
}
bool ok = true;
FOR(i,N) if(W[i] == 0 && !canFlip[i]) ok = false;
FOR(i,N) {
int cnt =0 ;
for(auto g : u.groups[i]){
if(W[g]==0) cnt++;
if(Flip1[g]){
cnt = 0 ; break;
}
}
if(cnt % 2 == 1) ok = false;
}
puts(ok ? "Yes" : "No");
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0