結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
|
提出日時 | 2024-01-27 18:40:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,450 bytes |
コンパイル時間 | 959 ms |
コンパイル使用メモリ | 85,648 KB |
最終ジャッジ日時 | 2025-02-19 00:28:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vector<int>D(N); for(int i=0;i<N;i++)cin>>D[i]; vector<int>W(N); for(int i=0;i<N;i++)cin>>W[i]; vector<vector<int>>G(N); vector<bool>check(N); for(int i=0;i<N;i++){ int u=(i+D[i])%N; int v=(i-D[i]%N+N)%N; if(u==v)check[u]=true; else{ G[u].push_back(v); G[v].push_back(u); } } vector<bool>flag(N); for(int i=0;i<N;i++){ if(flag[i])continue; queue<int>q; flag[i]=true; q.push(i); int cnt=0; if(W[i]==0)cnt++; bool ok=false; while(q.size()){ int x=q.front(); q.pop(); for(auto j:G[x]){ if(flag[j])continue; if(check[j])ok=true; flag[j]=true; q.push(j); if(W[j]==0)cnt++; } } if(!ok&&cnt%2==1){ cout<<"No"<<"\n"; return 0; } } cout<<"Yes"<<"\n"; }