結果

問題 No.2664 Prime Sum
ユーザー nu50218nu50218
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0