結果
問題 | No.583 鉄道同好会 |
ユーザー | yuppe19 😺 |
提出日時 | 2019-04-12 21:09:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,421 bytes |
コンパイル時間 | 760 ms |
コンパイル使用メモリ | 72,168 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 15:53:35 |
合計ジャッジ時間 | 2,219 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 |
ソースコード
#include <iostream>#include <vector>using namespace std;class UnionFind {vector<int> par;public:explicit UnionFind(int n) : par(n, -1) {}int root(int a) {if(par[a] < 0) { return a; }return par[a] = root(par[a]);}int size(int a) {return -par[root(a)];}void unite(int a, int b) {a = root(a);b = root(b);if(a == b) { return; }if(size(a) < size(b)) { swap(a, b); }par[a] += par[b];par[b] = a;}};template <class T>inline void readint(T *x) {*x = 0;int c;for(;;) {c = getchar_unlocked();switch(c) case 48: case 49: case 50: case 51: case 52: case 53: case 54: case 55: case 56: case 57: goto num;}num:for(;;) {switch(c) {case 48: case 49: case 50: case 51: case 52: case 53: case 54: case 55: case 56: case 57:*x *= 10;*x += c - 48;break;default:return;}c = getchar_unlocked();}}int main(void) {int N, M; readint(&N); readint(&M);UnionFind uf(N);vector<int> deg(N);int x = 0;for(int i=0; i<M; ++i) {int u, v; readint(&u); readint(&v);uf.unite(u, v);++deg[u];++deg[v];x = v;}int k = 0;for(int v=0; v<N; ++v) {if(!deg[v]) { continue; }if(deg[v] & 1) { ++k; }if(uf.root(x) != uf.root(v)) {puts("NO");return 0;}}puts(k == 0 || k == 2 ? "YES" : "NO");return 0;}