Submission #2243719


Source Code Expand

#include <limits>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>

using namespace std;

template<class F>
void times_do(size_t n, F func)
{
    for(size_t i = 0; i < n; ++i) func();
}

template<class T>
T read()
{
    T value;
    std::cin >> value;
    return value;
}

template<class T>
vector<T> reads(size_t n)
{
    vector<T> a;
    a.reserve(n);
    times_do(n, [&](){
        a.push_back(read<T>());
    });
    return a;
}

template<class T>
vector<vector<T>> reads(size_t n, size_t m)
{
    vector<vector<T>> a;
    a.reserve(n);
    times_do(n, [&](){
        a.push_back(reads<T>(m));
    });
    return a;
}

int count_paths(const vector<vector<bool>>& graph, size_t index, vector<bool>& visited)
{
    if(visited[index]) return 0;
    
    visited[index] = true;
    
    if(all_of(begin(visited), end(visited), [](auto x){ return x; }))
    {
        visited[index] = false;
        return 1;
    }
    
    int paths = 0;
    for(size_t i = 0; i != graph.size(); ++i)
    {
        if(i != index && graph[index][i])
        {
            paths += count_paths(graph, i, visited);
        }
    }
    
    visited[index] = false;
    return paths;
}

int count_paths(const vector<vector<bool>>& graph)
{
    vector<bool> visited(graph.size(), false);
    return count_paths(graph, 0, visited);
}

int main()
{
    const auto N = read<size_t>();
    const auto M = read<size_t>();
    
    vector<vector<bool>> graph(N, vector<bool>(N, false));
    
    times_do(M, [&](){
        int a,b;
        cin >> a >> b;
        a--;b--;
        graph[a][b] = graph[b][a] = true;
    });
    
    cout << count_paths(graph) << '\n';
    
    return 0;
}

Submission Info

Submission Time
Task C - One-stroke Path
User tetsurom
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1819 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 2
AC × 15
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.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
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 2 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_12.txt AC 1 ms 256 KB
subtask_1_13.txt AC 2 ms 256 KB