Submission #1818833

---

Source Code Expand

#[cfg(feature = "local")]
pub mod tests;

use std::io::*;
use std::str::FromStr;
use std::fmt::Debug;

pub fn main() {
    let i = stdin();
    solve(&mut i.lock(), &mut stdout());
}

pub fn solve(i: &mut BufRead, o: &mut Write) {
    let (n, m) = read_usizes(i);
    let mut buf = Vec::new();
    let mut g = make_graph(n, &mut buf);

    for _ in 0..m {
        let (x, y) = read_usizes(i);
        let (x, y) = (x - 1, y - 1);
        g[x][y - x - 1] = true;
    }

    // 派閥に所属する人物がmembersであるときに、[begin,end)から最大何人派閥に人物を追加できるかを返す
    fn get_addable(members: List<usize>, g: &[&mut [bool]], begin: usize, end: usize) -> usize {
        (begin..end)
            .map(|y| {
                if members.iter().cloned().all(|x| g[x][y - x - 1]) {
                    get_addable(members.cons(y), g, y + 1, end) + 1
                } else {
                    0
                }
            })
            .max()
            .unwrap_or(0)
    }
    let r = get_addable(List::new(), g.as_slice(), 0, n);
    writeln!(o, "{}", r).unwrap();
}
fn make_graph<'a>(nodes: usize, buf: &'a mut Vec<bool>) -> Vec<&'a mut [bool]> {
    buf.resize(nodes * (nodes - 1) / 2, false);
    let mut g = Vec::with_capacity(nodes);
    let mut s = buf.as_mut_slice();
    for n in 0..nodes {
        let s_old = s;
        let (mut head, mut tail) = s_old.split_at_mut(nodes - n - 1);
        s = tail;
        g.push(head);
    }
    assert!(s.len() == 0);
    g
}
enum List<'a, T: 'a> {
    None,
    Cons { head: T, tail: &'a List<'a, T> },
}
impl<'a, T: 'a> List<'a, T> {
    fn new() -> List<'static, T> {
        List::None
    }
    fn cons<'b>(&'b self, value: T) -> List<'b, T> {
        List::Cons {
            head: value,
            tail: self,
        }
    }
    fn iter(&self) -> &Self {
        self
    }
}
impl<'a, T: 'a> Iterator for &'a List<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        match *self {
            &List::None => None,
            &List::Cons { ref head, tail } => {
                *self = tail;
                Some(head)
            }
        }
    }
}

fn read_usizes(i: &mut BufRead) -> (usize, usize) {
    let line = read_line(i);
    let mut s = line.trim().split(' ');
    let r0 = read(&mut s);
    let r1 = read(&mut s);
    (r0, r1)
}

fn read_line(i: &mut BufRead) -> String {
    let mut line = String::new();
    i.read_line(&mut line).unwrap();
    line
}

fn read<'a, 'b, I, T>(i: &'a mut I) -> T
where
    I: Iterator<Item = &'b str>,
    T: FromStr,
    <T as FromStr>::Err: Debug,
{
    i.next().unwrap().parse().unwrap()
}

Submission Info

Compile Error

warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
  --> ./Main.rs:46:14
   |
46 |         let (mut head, mut tail) = s_old.split_at_mut(nodes - n - 1);
   |              ^^^^^^^^

Judge Result