結果

問題 No.583 鉄道同好会
コンテスト
ユーザー kkty
提出日時 2017-11-04 16:32:58
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 1,421 bytes
コンパイル時間 2,220 ms
コンパイル使用メモリ 177,228 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2024-11-23 17:55:49
合計ジャッジ時間 2,444 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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