結果
問題 | No.2664 Prime Sum |
ユーザー | nu50218 |
提出日時 | 2024-03-08 23:12:32 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,599 bytes |
コンパイル時間 | 1,948 ms |
コンパイル使用メモリ | 208,700 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-29 20:39:25 |
合計ジャッジ時間 | 2,837 ms |
ジャッジサーバーID (参考情報) |
judge4 / 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 xint 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 connectedbool same(int x, int y) {return leader(x) == leader(y);}// returns the size of component that x belongs toint 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;}