結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}