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
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
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 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