結果
問題 | No.2664 Prime Sum |
ユーザー |
|
提出日時 | 2024-03-08 23:12:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 1,599 bytes |
コンパイル時間 | 2,115 ms |
コンパイル使用メモリ | 200,104 KB |
最終ジャッジ日時 | 2025-02-20 03:03:12 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T = int> struct XorUnionFind { std::vector<int> d; std::vector<T> p; XorUnionFind(int n = 0) : d(n, -1), p(n, 0) {} // returns the leader of x int leader(int x) { if (d[x] < 0) return x; int r = leader(d[x]); p[x] ^= p[d[x]]; return d[x] = r; } // merge x and y with a condition that w = weight(y) ^ weight(x) bool merge(int x, int y, T w) { w ^= potential(x) ^ potential(y); x = leader(x); y = leader(y); if (x == y) return false; if (d[x] > d[y]) std::swap(x, y); d[x] += d[y]; d[y] = x; p[y] = w; return true; } // returns if x and y are connected bool same(int x, int y) { return leader(x) == leader(y); } // returns the size of component that x belongs to int size(int x) { return -d[leader(x)]; } // returns potential(x) := weight(x) ^ weight(leader(x)) long long potential(int x) { leader(x); return p[x]; } }; int main() { int n, m; cin >> n >> m; vector<pair<int, int>> ab; XorUnionFind<int> uf(n); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; ab.push_back({a, b}); uf.merge(a, b, 1); } for (int i = 0; i < m; i++) { auto [a, b] = ab[i]; if ((int)(uf.potential(a) ^ uf.potential(b)) == 0) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; }