結果
問題 | 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; }