結果
問題 | No.2664 Prime Sum |
ユーザー | ゆにぽけ |
提出日時 | 2024-03-08 21:13:21 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,809 bytes |
コンパイル時間 | 1,460 ms |
コンパイル使用メモリ | 134,172 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-29 18:53:12 |
合計ジャッジ時間 | 2,443 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <iterator>#include <string>#include <cctype>#include <cstring>#include <cstdlib>#include <cassert>#include <cmath>#include <ctime>#include <iomanip>#include <numeric>#include <stack>#include <queue>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <bitset>#include <random>#include <utility>#include <functional>using namespace std;#include<algorithm>#include<vector>#include<cassert>using namespace std;struct UnionFind{private:int n;vector<int> par,siz;public:UnionFind(int n) :n(n),par(n,-1),siz(n,1) {}int root(int u){assert(0 <= u && u < n);return (par[u] < 0 ? u:par[u] = root(par[u]));}bool same(int u,int v){assert(0 <= u && u < n && 0 <= v && v < n);return root(u) == root(v);}bool unite(int u,int v){assert(0 <= u && u < n && 0 <= v && v < n);u = root(u),v = root(v);if(u == v) return false;if(siz[u] < siz[v]) swap(u,v);siz[u] += siz[v];par[v] = u;return true;}int size(int u){assert(0 <= u && u < n);return siz[root(u)];}vector<vector<int>> components(){vector<vector<int>> ret(n);for(int u = 0;u < n;u++) ret[root(u)].push_back(u);ret.erase(remove_if(ret.begin(),ret.end(),[](vector<int> v) { return v.empty();}),ret.end());return ret;}};void Main(){int N,M;cin >> N >> M;UnionFind uf(2 * N);for(int i = 0;i < M;i++){int u,v;cin >> u >> v;u--; v--;uf.unite(u,v + N);uf.unite(u + N,v);}for(int i = 0;i < N;i++){if(uf.same(i,i + N)){cout << "No\n";return;}}cout << "Yes\n";}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) Main();}