結果

問題 No.583 鉄道同好会
ユーザー ryoissy
提出日時 2017-10-27 22:43:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 1,213 bytes
コンパイル時間 1,336 ms
コンパイル使用メモリ 165,756 KB
実行使用メモリ 15,616 KB
最終ジャッジ日時 2024-11-21 22:37:22
合計ジャッジ時間 2,285 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:64:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |                 scanf("%d%d",&f,&t);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,m;
vector<int> G[505];
bool used[505];
void visit(vector<vector<int> > &adj,int v,vector<int> &path){
    for(int i=0;i<G[v].size();i++){
        if(adj[v][G[v][i]]){
            adj[v][G[v][i]]--;
            adj[G[v][i]][v]--;
            visit(adj,G[v][i],path);
        }
    }
    path.push_back(v);
}
bool eulerPath(){
    int odd=0;
    int m=0;
    for(int i=0;i<n;i++){
        if(G[i].size()%2==1)odd++;
        m+=G[i].size();
    }
    m/=2;
    if(odd==0 || odd==2){
        vector<vector<int> > adj(n,vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=0;j<G[i].size();j++){
                adj[i][G[i][j]]++;
            }
        }
        vector<int> path;
        if(odd==0){
            for(int i=0;i<n;i++){
                if(used[i]){
                    visit(adj,i,path);
                    break;
                }
            }
            return path.size()==m+1;
        }else{
            for(int j=0;j<n;j++){
                if(G[j].size()%2!=0 && used[j]){
                    visit(adj,j,path);
                    break;
                }
            }
            return path.size()==m+1;
        }
    }
    return false;
}
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int f,t;
        scanf("%d%d",&f,&t);
        G[f].push_back(t);
        G[t].push_back(f);
        used[f]=true;
        used[t]=true;
    }
    printf("%s\n",eulerPath()?"YES":"NO");
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0