Submission #1221798
Source Code Expand
#include <bits/stdc++.h> using namespace std; constexpr int maxn = 1e5 + 100; int n, m; vector<int> vec[maxn]= {}, path; bitset<maxn> viz = 0; bool extend_path(){ const int cur = path.back(); while(!vec[cur].empty() && viz[vec[cur].back()]) vec[cur].pop_back(); if(vec[cur].empty()) return false; viz[vec[cur].back()] = 1; path.push_back(vec[cur].back()); return true; } int main(){ cin >> n >> m; for(int i = 0, a, b; i < m; ++i){ cin >> a >> b; vec[a].push_back(b); vec[b].push_back(a); } path.push_back(1); path.push_back(vec[1][0]); viz[1] = viz[vec[1][0]] = 1; while(extend_path()); reverse(begin(path), end(path)); while(extend_path()); cout << path.size() << endl; for(const auto x : path) cout << x << ' '; cout << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Hamiltonish Path |
User | tamionv |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 874 Byte |
Status | AC |
Exec Time | 99 ms |
Memory | 6776 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 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 | 2560 KB |
sample_02.txt | AC | 2 ms | 2560 KB |
sample_03.txt | AC | 2 ms | 2560 KB |
subtask_1_01.txt | AC | 79 ms | 4736 KB |
subtask_1_02.txt | AC | 21 ms | 3072 KB |
subtask_1_03.txt | AC | 72 ms | 4736 KB |
subtask_1_04.txt | AC | 83 ms | 4736 KB |
subtask_1_05.txt | AC | 86 ms | 4736 KB |
subtask_1_06.txt | AC | 84 ms | 4736 KB |
subtask_1_07.txt | AC | 92 ms | 5888 KB |
subtask_1_08.txt | AC | 88 ms | 5760 KB |
subtask_1_09.txt | AC | 99 ms | 6776 KB |
subtask_1_10.txt | AC | 26 ms | 3328 KB |
subtask_1_11.txt | AC | 32 ms | 3328 KB |
subtask_1_12.txt | AC | 2 ms | 2560 KB |
subtask_1_13.txt | AC | 2 ms | 2560 KB |