Submission #1241983
Source Code Expand
#include <iostream> #include <cstdio> #include <vector> #include <string> #include <algorithm> #include <set> #include <map> #define rep(i,n) for(int i=0; i<(n); i++) #define reps(i,x,n) for(int i=x; i<(n); i++) #define rrep(i,n) for(int i=(n)-1; i>=0; i--) #define all(X) (X).begin(),(X).end() #define X first #define Y second #define pb push_back #define eb emplace_back using namespace std; typedef long long int ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); } const ll INF = 0x3fffffff; int N, M; vector<int> v[100005], ans; bool f[100005] = {}; void dfs(int n){ ans.push_back(n); f[n] = true; for(auto t: v[n]) if( !f[t] ){ dfs(t); break; } } int main(){ //ios_base::sync_with_stdio(0); cin >> N >> M; rep(i,M){ int A, B; cin >> A >> B; //A--; B--; v[A].push_back(B); v[B].push_back(A); } int n = 1; while(1){ Fill(f, false); ans.clear(); dfs(n); reverse( all(ans) ); ans.pop_back(); dfs(n); bool check = true; for(auto t: v[ans.back()]) if(t == ans[0]) check = false; if( check ) break; n++; } cout << ans.size() << endl; for(auto a: ans){ cout << a; if(ans.back() != a) cout << " "; } cout << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Hamiltonish Path |
User | oyas |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1549 Byte |
Status | WA |
Exec Time | 103 ms |
Memory | 9720 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | 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 | AC | 2 ms | 2688 KB |
sample_02.txt | AC | 2 ms | 2688 KB |
sample_03.txt | AC | 2 ms | 2688 KB |
subtask_1_01.txt | AC | 82 ms | 4864 KB |
subtask_1_02.txt | AC | 20 ms | 3200 KB |
subtask_1_03.txt | AC | 71 ms | 4864 KB |
subtask_1_04.txt | AC | 84 ms | 4736 KB |
subtask_1_05.txt | AC | 84 ms | 4864 KB |
subtask_1_06.txt | AC | 85 ms | 4864 KB |
subtask_1_07.txt | AC | 90 ms | 5888 KB |
subtask_1_08.txt | AC | 89 ms | 5888 KB |
subtask_1_09.txt | AC | 103 ms | 9720 KB |
subtask_1_10.txt | WA | 40 ms | 3328 KB |
subtask_1_11.txt | WA | 47 ms | 3456 KB |
subtask_1_12.txt | WA | 2 ms | 2688 KB |
subtask_1_13.txt | AC | 2 ms | 2688 KB |