結果
問題 | No.583 鉄道同好会 |
ユーザー | hiyokko2 |
提出日時 | 2017-10-28 00:31:25 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 4,287 bytes |
コンパイル時間 | 840 ms |
コンパイル使用メモリ | 82,580 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-01 18:22:35 |
合計ジャッジ時間 | 1,715 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 6 ms
5,376 KB |
testcase_12 | AC | 7 ms
5,376 KB |
testcase_13 | AC | 8 ms
5,376 KB |
testcase_14 | AC | 8 ms
5,376 KB |
testcase_15 | AC | 9 ms
5,376 KB |
testcase_16 | AC | 17 ms
5,376 KB |
testcase_17 | AC | 20 ms
5,376 KB |
testcase_18 | AC | 20 ms
5,376 KB |
ソースコード
#include <iostream> #include <vector> #include <string.h> #include <stack> #include <queue> #include <algorithm> #include <climits> #include <cmath> #include <map> #include <set> #include <assert.h> #include <sstream> #define REP(i,n) for(ll i=0;i<(n);i++) #define MOD 1000000007 #define int long long #ifdef int const long long INF = LLONG_MAX / 10; #else const int INF = 1010101010; #endif using namespace std; typedef long long ll; typedef vector<vector<ll>> mat; typedef pair<int, int> P; //typedef pair<double, double> P; #ifdef LOCAL #define dump(...) \ do { \ std::ostringstream os; \ os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \ print_to(os, ", ", "\n", __VA_ARGS__); \ std::cerr << os.str(); \ } while (0) #define dump_(a) \ do { \ std::ostringstream os; \ os << __LINE__ << ":\t" << #a << " = ["; \ print_to_(os, ", ", "]\n", all(a)); \ std::cerr << os.str(); \ } while (0) #else #define dump(...) #define dump_(...) #endif template <typename T> void print_to(std::ostream &os, const char *, const char *tail, const T &fst) { os << fst << tail; } template <typename Fst, typename... Rst> void print_to(std::ostream &os, const char *del, const char *tail, const Fst &fst, const Rst &... rst) { os << fst << del; print_to(os, del, tail, rst...); } template <typename Iter> void print_to_(std::ostream &os, const char *del, const char *tail, Iter bgn, Iter end) { for (Iter it = bgn; it != end;) { os << *it; if (++it != end) { os << del; } else { os << tail; } } } template <typename Fst, typename... Rst> void println(const Fst &fst, const Rst &... rst) { print_to(std::cout, "\n", "\n", fst, rst...); } template <typename Fst, typename... Rst> void print(const Fst &fst, const Rst &... rst) { print_to(std::cout, " ", "\n", fst, rst...); } template <typename Iter> void println_(Iter bgn, Iter end) { print_to_(std::cout, "\n", "\n", bgn, end); } template <typename Iter> void print_(Iter bgn, Iter end) { print_to_(std::cout, " ", "\n", bgn, end); } // const int MOD = 1000000007; namespace trush { int _ = (std::cout.precision(10), std::cout.setf(std::ios::fixed), std::cin.tie(0), std::ios::sync_with_stdio(0), 0); } //UnionFind!!! class UnionFind { private: vector<int> par; vector<int> myRank; vector<int> cnt; public: //n要素で初期化 UnionFind(int n) { par.resize(n); myRank.resize(n); cnt.resize(n); REP(i,n) { par[i] = i; myRank[i] = 0; cnt[i] = 1; } } //木の根を求める int find(int x) { if (par[x] == x) return x; else return par[x] = find(par[x]); } //xとyの属する集合を併合 void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (myRank[x] < myRank[y]) { par[x] = y; cnt[y] += cnt[x]; } else { par[y] = x; cnt[x] += cnt[y]; if (myRank[x] == myRank[y]) myRank[x]++; } } //xとyが同じ集合に属するか否か bool same(int x, int y) { return find(x) == find(y); } //xが含まれる集合の要素数 int count(int x) { return cnt[find(x)]; } }; int N, M; int Sa, Sb; int degree[510]; signed main() { cin >> N >> M; UnionFind uf(N); int vNum = 0; REP(i,M) { cin >> Sa >> Sb; uf.unite(Sa, Sb); if (degree[Sa] == 0) vNum++; degree[Sa]++; if (degree[Sb] == 0) vNum++; degree[Sb]++; } int oddNum = 0; REP(i,N) if (degree[i] % 2 == 1) oddNum++; if (uf.count(Sa) == vNum && (oddNum == 0 || oddNum == 2)) { cout << "YES" << endl; } else { cout << "NO" << endl; } }