Submission #1499253


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // solve
    vector<bool> used(n);
    vector<int> path;
    function<void (int)> go = [&](int i) {
        path.push_back(i);
        used[i] = true;
        for (int j : g[i]) if (not used[j]) {
            go(j);
            break;
        }
    };
    go(0);
    reverse(whole(path));
    assert (path.back() == 0);
    used[0] = false;
    path.pop_back();
    go(0);
    // output
    printf("%d\n", int(path.size()));
    repeat (i, path.size()) {
        printf("%d%c", path[i] + 1, i + 1 == path.size() ? '\n' : ' ');
    }
    return 0;
}

Submission Info

Submission Time
Task B - Hamiltonish Path
User kimiyuki
Language C++14 (Clang 3.8.0)
Score 500
Code Size 1034 Byte
Status AC
Exec Time 52 ms
Memory 9720 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 19
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 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 31 ms 3968 KB
subtask_1_02.txt AC 8 ms 896 KB
subtask_1_03.txt AC 29 ms 4096 KB
subtask_1_04.txt AC 32 ms 3584 KB
subtask_1_05.txt AC 32 ms 3584 KB
subtask_1_06.txt AC 32 ms 3584 KB
subtask_1_07.txt AC 35 ms 5888 KB
subtask_1_08.txt AC 35 ms 5760 KB
subtask_1_09.txt AC 52 ms 9720 KB
subtask_1_10.txt AC 9 ms 896 KB
subtask_1_11.txt AC 11 ms 1024 KB
subtask_1_12.txt AC 1 ms 256 KB
subtask_1_13.txt AC 1 ms 256 KB