結果
問題 | No.2664 Prime Sum |
ユーザー |
|
提出日時 | 2024-03-08 21:05:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,289 bytes |
コンパイル時間 | 1,206 ms |
コンパイル使用メモリ | 82,304 KB |
最終ジャッジ日時 | 2025-02-20 01:52:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
#include <iostream> #include <cassert> #include <queue> using namespace std; template <typename T = int> struct Graph { public: using value_type = T; struct Edge { int from, to; T cost; int id; operator int() const { return to; } }; Graph() {} Graph(int n) : n(n), m(0), g(n) {} void add_directed_edge(int from, int to, T cost = 1) { assert(0 <= from && from < n); assert(0 <= to && to < n); g[from].push_back((Edge){from, to, cost, m++}); } void add_undirected_edge(int from, int to, T cost = 1) { assert(0 <= from && from < n); assert(0 <= to && to < n); g[from].push_back((Edge){from, to, cost, m}); g[to].push_back((Edge){to, from, cost, m++}); } int size() { return n; } int edge_size() { return m; } inline const std::vector<Edge> &operator[](const int &u) const { return g[u]; } inline std::vector<Edge> &operator[](const int &u) { return g[u]; } private: int n, m; std::vector<std::vector<Edge>> g; }; std::vector<int> is_bipartite(Graph<int> &g) // b[n] == 1 <=> g is bipartite { int n = g.size(); std::vector<int> b(n + 1, -1); b[n] = 0; std::queue<int> que; for (int i = 0; i < n; i++) { if (b[i] != -1) { continue; } b[i] = 0; que.push(i); while (que.size()) { int u = que.front(); que.pop(); for (int v : g[u]) { if (b[u] == b[v]) { return b; } if (b[v] == -1) { b[v] = 1 - b[u]; que.push(v); } } } } b[n] = 1; return b; } int main() { int n, m; cin >> n >> m; Graph g(n); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; g.add_undirected_edge(a, b); } vector<int> b = is_bipartite(g); if(b[n]) { cout << "Yes" << endl; } else { cout << "No" << endl; } }