Submission #1988558


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,m;
  cin>>n>>m;
  vector<vi> g(n);
  rep(i,m){
      int a,b;
      cin>>a>>b;
      a--;b--;
      g[a].push_back(b);
      g[b].push_back(a);
  }

  vector<bool> used(n,false);
  vi path;
  int pt=0;
  rep(i,n) if(g[i].size()>0){
    pt=i;
    break;
  }

  while(1){
    bool c=false;
    rep(j,g[pt].size()){
        int next=g[pt][j];
        if(used[next]==false){
            pt=next;
            path.push_back(pt);
            used[next]=true;
            c=true;
            break;
        }
    }
    if(c==false)break;
  }

  pt=path[0];
  reverse(all(path));

  while(1){
    bool c=false;
    rep(j,g[pt].size()){
        int next=g[pt][j];
        if(used[next]==false){
            pt=next;
            path.push_back(pt);
            used[next]=true;
            c=true;
            break;
        }
    }
    if(c==false)break;
  }

  cout<<path.size()<<endl;
  rep(i,path.size()){
     cout<<path[i]+1;
     if(i<path.size()-1)cout<<" ";
     else cout<<endl;
  }                      

}

Submission Info

Submission Time
Task B - Hamiltonish Path
User rika0384
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1725 Byte
Status
Exec Time 97 ms
Memory 6776 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 500 / 500 sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_01.txt 66 ms 3968 KB
subtask_1_02.txt 17 ms 896 KB
subtask_1_03.txt 60 ms 4096 KB
subtask_1_04.txt 71 ms 3584 KB
subtask_1_05.txt 70 ms 3584 KB
subtask_1_06.txt 70 ms 3584 KB
subtask_1_07.txt 75 ms 5888 KB
subtask_1_08.txt 73 ms 5760 KB
subtask_1_09.txt 97 ms 6776 KB
subtask_1_10.txt 23 ms 896 KB
subtask_1_11.txt 26 ms 1024 KB
subtask_1_12.txt 1 ms 256 KB
subtask_1_13.txt 1 ms 256 KB