Submission #10312298
Source Code Expand
use std::vec::Vec;
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}
fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
let v: Vec<T> = read_vec();
assert_eq!(v.len(), 2);
(v[0], v[1])
}
fn main() {
solve();
}
fn solve() {
let (n, m) = read_touple::<usize>();
let mut g = vec![vec![]; n];
for _ in 0..m {
let (a, b) = read_touple::<usize>();
g[a-1].push(b-1);
g[b-1].push(a-1);
}
let mut visited = vec![false; n];
visited[0] = true;
let ans = dfs_rec(0, &g, &mut visited);
//let ans = dfs_loop(n, &g);
println!("{}", ans);
}
fn dfs_rec(v: usize, g: &Vec<Vec<usize>>, visited: &mut Vec<bool>) -> usize {
let mut all_visited = visited
.iter()
.fold(true, |acc, &x| acc && x);
if all_visited {
return 1;
}
let mut res = 0;
for &e in &g[v] {
if visited[e] {
continue
}
visited[e] = true;
res += dfs_rec(e, g, visited);
visited[e] = false;
}
return res
}
// stack に訪問状況の情報も付随しないと解けない
fn dfs_loop(n: usize, g: &Vec<Vec<usize>>) -> usize {
let mut res = 0;
let mut stack = Vec::new();
// init
let now = 0;
let visited = vec![false; n];
stack.push((now, visited));
while let Some(t) = stack.pop() {
let (now, mut visited) = t;
visited[now] = true;
let all_visited = visited
.iter()
.fold(true, |acc, &x| acc && x);
if all_visited {
res += 1;
continue
}
for &e in &g[now] {
if visited[e] {
continue
}
stack.push((e, visited.clone()));
}
}
res
}
Submission Info
Submission Time
2020-02-23 22:08:46+0900
Task
C - One-stroke Path
User
pod
Language
Rust (1.15.1)
Score
300
Code Size
2032 Byte
Status
AC
Exec Time
2 ms
Memory
4352 KB
Compile Error
warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
--> ./Main.rs:43:7
|
43 | let mut all_visited = visited
| ^^^^^^^^^^^^^^^
warning: function is never used: `dfs_loop`, #[warn(dead_code)] on by default
--> ./Main.rs:68:1
|
68 | fn dfs_loop(n: usize, g: &Vec<Vec<usize>>) -> usize {
| ^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
300 / 300
Status
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
2 ms
4352 KB
sample_02.txt
AC
2 ms
4352 KB
subtask_1_01.txt
AC
2 ms
4352 KB
subtask_1_02.txt
AC
2 ms
4352 KB
subtask_1_03.txt
AC
2 ms
4352 KB
subtask_1_04.txt
AC
2 ms
4352 KB
subtask_1_05.txt
AC
2 ms
4352 KB
subtask_1_06.txt
AC
2 ms
4352 KB
subtask_1_07.txt
AC
2 ms
4352 KB
subtask_1_08.txt
AC
2 ms
4352 KB
subtask_1_09.txt
AC
2 ms
4352 KB
subtask_1_10.txt
AC
2 ms
4352 KB
subtask_1_11.txt
AC
2 ms
4352 KB
subtask_1_12.txt
AC
2 ms
4352 KB
subtask_1_13.txt
AC
2 ms
4352 KB