結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
|
提出日時 | 2019-09-03 16:49:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,635 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 178,960 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 06:17:10 |
合計ジャッジ時間 | 2,658 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;class UnionFind {private:vector<int> data;public:UnionFind(const int& N) : data(vector<int>(N, -1)) {}int root(const int& x) {if (data[x] < 0) {return x;} else {return data[x] = root(data[x]);}}int size(const int& x) {return -data[root(x)];}bool same(const int& x, const int& y) {return root(x) == root(y);}void unite(int x, int y) {if (same(x, y)) return;x = root(x);y = root(y);if (size(x) < size(y)) {data[y] += data[x];data[x] = y;} else {data[x] += data[y];data[y] = x;}}};int main() {int N;cin >> N;int D[N], W[N];bool flag[N] = {};for (int i = 0; i < N; i++) cin >> D[i];for (int i = 0; i < N; i++) cin >> W[i];UnionFind UF(N);for (int i = 0; i < N; i++) {int x = (i + D[i]) % N;int y = ((i - D[i]) % N + N) % N;UF.unite(x, y);if (x == y) {flag[x] = true;}}map<int, vector<int>> sets;for (int i = 0; i < N; i++) {sets[UF.root(i)].push_back(i);}for (const auto& s : sets) {int cnt = s.second.size();bool is_flaged = false;for (const auto& x : s.second) {is_flaged |= flag[x];cnt -= W[x];}if (is_flaged) continue;if (cnt % 2) {cout << "No" << endl;return 0;}}cout << "Yes" << endl;}