結果

問題 No.583 鉄道同好会
ユーザー kktykkty
提出日時 2017-11-04 16:32:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 1,421 bytes
コンパイル時間 1,499 ms
コンパイル使用メモリ 178,488 KB
実行使用メモリ 9,344 KB
最終ジャッジ日時 2024-05-02 22:44:23
合計ジャッジ時間 2,628 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 14 ms
5,376 KB
testcase_12 AC 20 ms
5,632 KB
testcase_13 AC 21 ms
5,632 KB
testcase_14 AC 21 ms
5,632 KB
testcase_15 AC 24 ms
6,272 KB
testcase_16 AC 46 ms
8,576 KB
testcase_17 AC 56 ms
9,344 KB
testcase_18 AC 57 ms
9,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define ALL(a) (a).begin(),(a).end()
#define MOD 1000000007
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 30);
typedef pair<ll,ll> pii;
struct Edge{ ll s,t,c; };
typedef vector<vector<ll>> Graph;
typedef vector<pii> vpii;

vi getDist(Graph graph,ll r) {
  ll V=graph.size();
  vi dist(V); REP(i,V) dist[i]=INF;
  priority_queue<pii,vpii,greater<pii>> pq;
  dist[r]=0; pq.push({0ll,r});
  while(pq.size()){
    ll s=pq.top().second;
    for(ll to:graph[s]) if(dist[to] > dist[s]+1) {
      dist[to]=dist[s]+1;
      pq.push({dist[to],to});
    }
    pq.pop();
  }
  return dist;
}

int main() {
  ll N,M; cin>>N>>M;
  Graph G(N);
  vi a(M),b(M);

  REP(i,M) cin>>a[i]>>b[i];
  REP(i,M) {
    G[a[i]].PB(b[i]);
    G[b[i]].PB(a[i]);
  }
  unordered_map<ll,ll> cnt;
  REP(i,M) {
    cnt[a[i]]+=1;
    cnt[b[i]]+=1;
  }
  {
    vi dist=getDist(G,a[0]);
    for(auto p:cnt) {
      if(dist[p.first]==INF) {
        cout<<"NO"<<endl;
        return 0;
      }
    }
  }
  {
    ll c=0;
    for(auto p:cnt) {
      if(p.second%2) c++;
    }
    if(c<=2) {
      cout<<"YES"<<endl;
    } else{
      cout<<"NO"<<endl;
    }
    return 0;
  }
}
0