Submission #1221800
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define sqr(x) ((x) * (x))
#define pb push_back
#define mp make_pair
#define ins insert
#define er erase
#define bg begin()
#define ed end()
#define f first
#define s second
#define fin(name) freopen(name, "r", stdin)
#define fout(name) freopen(name, "w", stdout)
#define files(name) fin(name".in"); fout(name".out")
#define enter cout << "\n"
#define space cout << " "
#define endl "\n"
#define fi(st,n) for (int i = (st); i <= (n); ++i)
#define fj(st,n) for (int j = (st); j <= (n); ++j)
#define fk(st,n) for (int k = (st); k <= (n); ++k)
#define fq(st,n) for (int q = (st); q <= (n); ++q)
#define fw(st,n) for (int w = (st); w <= (n); ++w)
#define ff(i, st, n) for (int (i) = (st); (i) <= (n); ++(i))
#define ei(st,n) for (int i = (st); i >= (n); --i)
#define ej(st,n) for (int j = (st); j >= (n); --j)
#define ek(st,n) for (int k = (st); k >= (n); --k)
#define ef(i, st, n) for (int (i) = (st); (i) >= (n); --(i))
#define ri(st,n) for (int i = (st); i < (n); ++i)
#define rj(st,n) for (int j = (st); j < (n); ++j)
#define rk(st,n) for (int k = (st); k < (n); ++k)
#define rq(st,n) for (int q = (st); q < (n); ++q)
#define rf(i, st, n) for (int (i) = (st); (i) < (n); ++(i))
#define clean(a) memset((a),0,sizeof (a))
#define sync ios_base::sync_with_stdio(0);cin.tie(0)
#define y1 dsklmlvmd
typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int inf = (int)1e9;
const dbl eps = (dbl) 1e-8;
const int mod = (int) 1e9 + 7;
const int maxn = (int) 1e5 + 5;
//const dbl M_PI = (dbl)2 * (dbl)acos(0);
//cout<<fixed<<setprecision(10);
//srand(time(0));
int n, m, dc;
int t[maxn];
vector <int> vc[2];
vector <pii> a[maxn];
void dfs(int v) {
t[v] = 1;
vc[dc].pb(v);
ri(0, a[v].size()) {
if (!t[a[v][i].f]) {
dfs(a[v][i].f);
break;
}
}
return;
}
int main() {
// fin("t.in");
sync;
cin >> n >> m;
fi(1, m) {
int u, v;
cin >> u >> v;
a[u].pb(mp(v, i));
a[v].pb(mp(u, i));
}
clean(t);
vc[0].clear();
dc = 0;
dfs(1);
dc = 1;
vc[1].clear();
dfs(1);
cout << (int)vc[0].size() + (int)vc[1].size() - 1 << endl;
ei((int)vc[1].size() - 1, 1) {
cout << vc[1][i] << " ";
}
ri(0, vc[0].size()) {
cout << vc[0][i] << " ";
}
cout << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Hamiltonish Path |
User |
mHuman |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2577 Byte |
Status |
AC |
Exec Time |
55 ms |
Memory |
9976 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 |
3 ms |
2944 KB |
sample_02.txt |
AC |
3 ms |
2944 KB |
sample_03.txt |
AC |
3 ms |
2944 KB |
subtask_1_01.txt |
AC |
34 ms |
6144 KB |
subtask_1_02.txt |
AC |
10 ms |
3840 KB |
subtask_1_03.txt |
AC |
34 ms |
5760 KB |
subtask_1_04.txt |
AC |
36 ms |
6144 KB |
subtask_1_05.txt |
AC |
34 ms |
6144 KB |
subtask_1_06.txt |
AC |
35 ms |
6144 KB |
subtask_1_07.txt |
AC |
37 ms |
6784 KB |
subtask_1_08.txt |
AC |
36 ms |
6656 KB |
subtask_1_09.txt |
AC |
55 ms |
9976 KB |
subtask_1_10.txt |
AC |
11 ms |
4352 KB |
subtask_1_11.txt |
AC |
13 ms |
4480 KB |
subtask_1_12.txt |
AC |
3 ms |
2944 KB |
subtask_1_13.txt |
AC |
3 ms |
2944 KB |