結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2015-04-13 07:12:42 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 925 bytes |
コンパイル時間 | 1,175 ms |
コンパイル使用メモリ | 160,096 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 14:10:00 |
合計ジャッジ時間 | 2,257 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define MAX 500 int dp[MAX]; bool check[MAX]; int finduni(int a){ if (dp[a] < 0) return a; else return dp[a] = finduni(dp[a]); } bool connect(int a, int b){ a = finduni(a); b = finduni(b); if (a == b) return false; dp[a] += dp[b] + 1; check[a] |= check[b]; dp[b] = a; return true; } int main(){ int N; cin >> N; vector<int> D(N), W(N); for (int i = 0; i < N; i++) { cin >> D[i]; } for (int i = 0; i < N; i++) { cin >> W[i]; } for (int i = 0; i < N; i++) { dp[i] = -1; if (!W[i]) dp[i]--; check[i] = false; } for (int i = 0; i < N; i++) { int a = (i + D[i]) % N; int b = (i - D[i]) % N; if (b < 0) b += N; if (a == b) check[finduni(a)] = true; else connect(a, b); } for (int i = 0; i < N; i++) { if (dp[i] >= 0) continue; if (!check[i] && dp[i] % 2 == 0){ cout << "No" << endl; return 0; } } cout << "Yes" << endl; }