Submission #37444520

---

Source Code Expand

// -*- coding:utf-8-unix -*-
// rustup doc --std --toolchain 1.42.0

#![allow(unused_imports)]
#![allow(unused_macros)]
use bitset_fixed::BitSet;
use im_rc::hashmap::OccupiedEntry;
use itertools::*;
use num::integer::*;
use petgraph::algo::*;
use petgraph::graph::{DiGraph, Graph, NodeIndex, UnGraph};
use petgraph::unionfind::UnionFind;
use petgraph::visit::{
    Bfs, Dfs, EdgeRef, IntoEdges, NodeCount, NodeIndexable, VisitMap, Visitable,
};
//use proconio::{input, marker::{Bytes, Chars, Isize1, Usize1}, source::{auto::AutoSource, line::LineSource, once::OnceSource}};
use rand::{
    distributions::WeightedIndex,
    prelude::{thread_rng, Distribution},
    seq::SliceRandom,
    Rng,
};
use regex::Regex;
use std::collections::*;
use std::io::{stderr, stdin, stdout, BufRead, BufReader, BufWriter, Read, Write};
use superslice::Ext;

/// input macros based on tanakh's input macro / proconio-rs.
/// tanakh's input macro: <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8>
/// proconio-rs: <https://docs.rs/proconio/0.3.8/proconio/>
/// this macro recieve `Iterator<Item = u8>` input source, except for Bytes/Chars/String read
/// ProconIBufIter receive `std::io::BufRead` trait. (`std::io::StdinLock`, `std::io::BufReader`, `&[u8]`, etc.)
#[allow(unused)]
macro_rules! finput_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = fread_value!($iter, $t);
        finput_inner!{$iter $($r)*}
    };
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = fread_value!($iter, $t);
        finput_inner!{$iter $($r)*}
    };
}
#[allow(unused)]
macro_rules! fread_value {
    ($iter:expr, ( $($t:tt),* )) => { ( $(fread_value!($iter, $t)),* ) };
    ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| fread_value!($iter, $t)).collect::<Vec<_>>() };
    ($iter:expr, u128) => { $iter.parse_uint::<u128>() };
    ($iter:expr, usize) => { $iter.parse_uint::<usize>() };
    ($iter:expr, usize1) => { $iter.parse_uint::<usize>() - 1 };
    ($iter:expr, u64) => { $iter.parse_uint::<u64>() };
    ($iter:expr, u64_1) => { $iter.parse_uint::<u64>() - 1 };
    ($iter:expr, u32) => { $iter.parse_uint::<u32>() };
    ($iter:expr, u32_1) => { $iter.parse_uint::<u32>() - 1 };
    ($iter:expr, u16) => { $iter.parse_uint::<u16>() };
    ($iter:expr, u8) => { $iter.parse_uint::<u8>() };
    ($iter:expr, i128) => { $iter.parse_iint::<i128>() };
    ($iter:expr, isize) => { $iter.parse_iint::<isize>() };
    ($iter:expr, i64) => { $iter.parse_iint::<i64>() };
    ($iter:expr, i32) => { $iter.parse_iint::<i32>() };
    ($iter:expr, i16) => { $iter.parse_iint::<i16>() };
    ($iter:expr, i8) => { $iter.parse_iint::<i16>() as i8 };
    ($iter:expr, byte) => { $iter.get_ascii_byte().unwrap() };
    ($iter:expr, Bytes) => {{ let mut v = vec![];$iter.get_ascii_bytes(&mut v);v }};
    ($iter:expr, Chars) => {{ let mut v = vec![];$iter.get_ascii_chars(&mut v);v }};
    ($iter:expr, String) => {{ let mut v = vec![];$iter.get_ascii_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
    ($iter:expr, LineBytes) => {{ let mut v = vec![];$iter.get_ascii_line_bytes(&mut v).and(Some(v)).unwrap() }};
    ($iter:expr, LineBytesTrim) => {{ let mut v = vec![];$iter.get_ascii_line_bytes_trim(&mut v);v }};
    ($iter:expr, LineString) => {{ let mut v = vec![];$iter.get_ascii_line_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
    ($iter:expr, LineStringTrim) => {{ let mut v = vec![];$iter.get_ascii_line_bytes_trim(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
    ($iter:expr, Utf8Bytes) => {{ let mut v = vec![];$iter.get_utf8_bytes(&mut v);v }};
    ($iter:expr, Utf8String) => {{ let mut v = vec![];$iter.get_utf8_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
    ($iter:expr, Utf8LineBytes) => {{ let mut v = vec![];$iter.get_utf8_line_bytes(&mut v);v }};
    ($iter:expr, Utf8LineBytesTrim) => {{ let mut v = vec![];$iter.get_utf8_line_bytes_trim(&mut v);v }};
    ($iter:expr, Utf8LineString) => {{ let mut v = vec![];$iter.get_utf8_line_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
    ($iter:expr, Utf8LineStringTrim) => {{ let mut v = vec![];$iter.get_utf8_line_bytes_trim(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
    ($iter:expr, $t:ty) => {{ let mut v = vec![];unsafe { std::string::String::from_utf8_unchecked($iter.get_utf8_bytes(&mut v).and(Some(v)).unwrap()) }.parse::<$t>().expect("Parse error") }};
}

fn solve() {
    let stdin = std::io::stdin();
    let mut source = ProconIBufIter::new(stdin.lock());
    macro_rules! finput { ($($r:tt)*) => { finput_inner!{source, $($r)*} }; }
    //use std::io::Write;
    //let out = std::io::stdout();
    //let mut out = std::io::BufWriter::new(out.lock());
    //let err = std::io::stderr();
    //let mut err = std::io::BufWriter::new(err.lock());
    finput! {
        n: usize,
    }
    // 座標圧縮 & UnionFind
    let mut fcvec = Vec::<u32>::with_capacity(n * 2 + 1);
    fcvec.push(1);
    let mut fcmap = HashMap::<u32, u32>::with_capacity(n * 2 + 1);
    fcmap.insert(1, 0);
    let mut uf = UnionFind::<u32>::new(n * 2 + 1);
    for _ in 0..n {
        use std::collections::hash_map::Entry::*;
        finput! {
            a: u32, b: u32,
        }
        let ai = match fcmap.entry(a) {
            Occupied(e) => { *e.get() },
            Vacant(e) => {
                let i = fcvec.len() as u32;
                fcvec.push(a);
                e.insert(i);
                i
            },
        };
        let bi = match fcmap.entry(b) {
            Occupied(e) => { *e.get() },
            Vacant(e) => {
                let i = fcvec.len() as u32;
                fcvec.push(b);
                e.insert(i);
                i
            },
        };
        uf.union(ai, bi);
    }
    // UnionFindの結果
    let infos = uf.into_labeling();
    let root = infos[0];
    // 最大到達解
    let mut max_floor = 1;
    for (fi, &firoot) in infos.iter().enumerate() {
        if root == firoot {
            max_floor.chmax(fcvec[fi as usize]);
        }
    }
    // 出力
    println!("{}", max_floor);
    //writeln!(&mut out, "{}", count).unwrap();
    //writeln!(&mut err, "{}", count).unwrap();
    //out.flush().unwrap();
    //err.flush().unwrap();
}

fn main() {
    solve()
    /*
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 134_217_728; // 128 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
    */
}

/// chmax, chmin sugar syntax
trait Change {
    fn chmax(&mut self, x: Self);
    fn chmin(&mut self, x: Self);
}
impl<T: PartialOrd> Change for T {
    fn chmax(&mut self, x: T) {
        if *self < x {
            *self = x;
        }
    }
    fn chmin(&mut self, x: T) {
        if *self > x {
            *self = x;
        }
    }
}
/// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator<Item = u8>`
pub struct ProconIBufIter<R: std::io::BufRead> {
    inner: R,
    raw: *const u8,
    len: usize,
    ptr: *const u8,
    end: *const u8,
}
unsafe fn ptr_offset_u8(dist: *const u8, origin: *const u8) -> usize {
    // Rust 1.47.0 or later, `dist.offset_from(origin) as usize`
    // <https://doc.rust-lang.org/std/primitive.pointer.html#method.offset_from>
    dist as usize - origin as usize
}
impl<R: std::io::BufRead> ProconIBufIter<R> {
    /// consume raw buffer
    #[allow(unused)]
    fn consume(&mut self, amt: usize) {
        let remain = unsafe { ptr_offset_u8(self.end, self.ptr) };
        assert!(remain >= amt);
        unsafe {
            self.ptr = self.ptr.add(amt);
        }
    }
    /// read when buffer is empty
    unsafe fn inner_read(&mut self) -> bool {
        assert!(self.is_empty());
        self.inner.consume(self.len);
        let buffer = self.inner.fill_buf().unwrap();
        let raw = buffer.as_ptr();
        let len = buffer.len();
        self.raw = raw;
        self.len = len;
        self.ptr = raw;
        self.end = raw.add(len);
        self.len > 0
    }
    /// check end of buffer
    fn is_empty(&self) -> bool {
        self.ptr == self.end
    }
    /// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator<Item = u8>`
    #[allow(unused)]
    fn new(inner: R) -> Self {
        let mut bufiter = Self {
            inner,
            raw: std::ptr::null(),
            len: 0,
            ptr: std::ptr::null(),
            end: std::ptr::null(),
        };
        unsafe { bufiter.inner_read() };
        bufiter
    }
    /// next(), but return empty value
    #[allow(unused)]
    fn next_unread(&mut self) -> Option<()> {
        if self.is_empty() && unsafe { !self.inner_read() } {
            return None;
        }
        unsafe {
            self.ptr = self.ptr.add(1);
        }
        return Some(());
    }
    /// get now pointer & increment pointer
    unsafe fn next_unchecked(&mut self) -> u8 {
        let p = self.ptr;
        self.ptr = p.add(1);
        *p
    }
    /// peek
    #[allow(unused)]
    fn peek(&mut self) -> Option<&u8> {
        if !self.is_empty() || unsafe { self.inner_read() } {
            unsafe { Some(&*self.ptr) }
        } else {
            None
        }
    }
    /// raw buffer
    #[allow(unused)]
    fn raw_buf(&mut self) -> &[u8] {
        if self.is_empty() {
            unsafe {
                self.inner_read();
            }
        }
        unsafe { std::slice::from_raw_parts(self.ptr, ptr_offset_u8(self.end, self.ptr)) }
    }
    /// skip unmatch bytes
    fn skipuntil_bytes_fn<F: FnMut(u8) -> bool>(&mut self, f: &mut F) -> bool {
        loop {
            let mut ptr = self.ptr;
            while ptr != self.end {
                if f(unsafe { *ptr }) {
                    self.ptr = ptr;
                    return true;
                }
                unsafe {
                    ptr = ptr.add(1);
                }
            }
            self.ptr = ptr;
            if unsafe { !self.inner_read() } {
                return false;
            }
        }
    }
}
impl<R: std::io::BufRead> Iterator for ProconIBufIter<R> {
    type Item = u8;
    /// fetch next byte
    fn next(&mut self) -> Option<Self::Item> {
        if !self.is_empty() || unsafe { self.inner_read() } {
            unsafe { Some(self.next_unchecked()) }
        } else {
            None
        }
    }
    /// remain size hint
    fn size_hint(&self) -> (usize, Option<usize>) {
        (unsafe { ptr_offset_u8(self.end, self.ptr) }, None)
    }
}
impl<R: std::io::BufRead> Drop for ProconIBufIter<R> {
    /// Saving the pointer on interruption
    fn drop(&mut self) {
        self.inner
            .consume(unsafe { ptr_offset_u8(self.ptr, self.raw) });
    }
}
/// speed frenzy input parser for program compete (fail parse may cause panic)
trait ProconParse {
    /// parse unsigned integer
    fn parse_uint<
        U: Copy
            + std::cmp::Ord
            + std::ops::BitAnd<Output = U>
            + std::ops::Add<Output = U>
            + std::ops::Sub<Output = U>
            + std::ops::Mul<Output = U>
            + std::convert::From<u8>,
    >(
        &mut self,
    ) -> U;
    /// parse signed integer
    fn parse_iint<
        I: Copy
            + std::cmp::Ord
            + std::ops::BitAnd<Output = I>
            + std::ops::Add<Output = I>
            + std::ops::Sub<Output = I>
            + std::ops::Mul<Output = I>
            + std::convert::From<u8>
            + std::ops::Neg<Output = I>,
    >(
        &mut self,
    ) -> I;
    /// get char (printable ascii char)
    fn parse_byte(&mut self) -> Option<u8>;
    /// get chars (printable ascii word)
    fn parse_bytes(&mut self) -> Vec<u8>;
    /// get line chars (sp+printable ascii)
    fn parse_line_bytes(&mut self) -> Vec<u8>;
    /// get line chars (trimed sp+printable ascii)
    fn parse_line_bytes_trim(&mut self) -> Vec<u8>;
}
/// speed frenzy input byte reader for program compete
trait ProconBytes {
    /// get bytes
    fn get_bytes_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<u8>, f: &mut F);
    /// get chars
    fn get_ascii_chars_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<char>, f: &mut F);
    /// get byte (printable ascii char)
    fn get_ascii_byte(&mut self) -> Option<u8>;
    /// get bytes (printable ascii word)
    fn get_ascii_bytes(&mut self, vec: &mut Vec<u8>);
    /// get chars (printable ascii word)
    fn get_ascii_chars(&mut self, vec: &mut Vec<char>);
    /// get line bytes (sp+printable ascii)
    fn get_ascii_line_bytes(&mut self, vec: &mut Vec<u8>);
    /// get line bytes (trimed sp+printable ascii)
    fn get_ascii_line_bytes_trim(&mut self, vec: &mut Vec<u8>);
    /// get bytes (printable utf8 word)
    fn get_utf8_bytes(&mut self, vec: &mut Vec<u8>);
    /// get line bytes (sp+printable utf8)
    fn get_utf8_line_bytes(&mut self, vec: &mut Vec<u8>);
    /// get line bytes (trimed sp+printable utf8)
    fn get_utf8_line_bytes_trim(&mut self, vec: &mut Vec<u8>);
}
impl<T: Iterator<Item = u8>> ProconParse for T {
    fn parse_uint<
        U: Copy
            + std::cmp::Ord
            + std::ops::BitAnd<Output = U>
            + std::ops::Add<Output = U>
            + std::ops::Sub<Output = U>
            + std::ops::Mul<Output = U>
            + std::convert::From<u8>,
    >(
        &mut self,
    ) -> U {
        loop {
            match self.next() {
                Some(c @ b'0'..=b'9') => {
                    let mut x = U::from(c.wrapping_sub(b'0'));
                    while let Some(c @ b'0'..=b'9') = self.next() {
                        x = x.mul(U::from(10)).add(U::from(c.wrapping_sub(b'0')));
                    }
                    break x;
                }
                Some(_) => continue,
                None => break U::from(0),
            }
        }
    }
    fn parse_iint<
        I: Copy
            + std::cmp::Ord
            + std::ops::BitAnd<Output = I>
            + std::ops::Add<Output = I>
            + std::ops::Sub<Output = I>
            + std::ops::Mul<Output = I>
            + std::ops::Neg<Output = I>
            + std::convert::From<u8>,
    >(
        &mut self,
    ) -> I {
        loop {
            match self.next() {
                Some(c @ b'0'..=b'9') => {
                    let mut x = I::from(c.wrapping_sub(b'0'));
                    while let Some(c @ b'0'..=b'9') = self.next() {
                        x = x.mul(I::from(10)).add(I::from(c.wrapping_sub(b'0')));
                    }
                    break x;
                }
                Some(b'-') => {
                    let mut x = if let Some(c @ b'0'..=b'9') = self.next() {
                        I::from(c.wrapping_sub(b'0')).neg()
                    } else {
                        break I::from(0);
                    };
                    while let Some(c @ b'0'..=b'9') = self.next() {
                        x = x.mul(I::from(10)).sub(I::from(c.wrapping_sub(b'0')));
                    }
                    break x;
                }
                Some(_) => continue,
                None => break I::from(0),
            }
        }
    }
    fn parse_byte(&mut self) -> Option<u8> {
        loop {
            match self.next() {
                Some(c @ b'!'..=b'~') => break Some(c),
                Some(_) => continue,
                None => break None,
            }
        }
    }
    fn parse_bytes(&mut self) -> Vec<u8> {
        let mut v = vec![];
        loop {
            match self.next() {
                Some(c @ b'!'..=b'~') => {
                    v.push(c);
                    while let Some(c @ b'!'..=b'~') = self.next() {
                        v.push(c);
                    }
                    break v;
                }
                Some(_) => continue,
                None => break v,
            }
        }
    }
    fn parse_line_bytes(&mut self) -> Vec<u8> {
        let mut v = vec![];
        loop {
            match self.next() {
                Some(c @ b' '..=b'~') => {
                    v.push(c);
                    while let Some(c @ b' '..=b'~') = self.next() {
                        v.push(c);
                    }
                    break v;
                }
                Some(_) => continue,
                None => break v,
            }
        }
    }
    fn parse_line_bytes_trim(&mut self) -> Vec<u8> {
        let mut v = vec![];
        loop {
            match self.next() {
                Some(c @ b'!'..=b'~') => {
                    v.push(c);
                    while let Some(c @ b' '..=b'~') = self.next() {
                        v.push(c);
                    }
                    while v.last() == Some(&b' ') {
                        v.pop();
                    }
                    break v;
                }
                Some(_) => continue,
                None => break v,
            }
        }
    }
}
impl<R: std::io::BufRead> ProconBytes for ProconIBufIter<R> {
    /// get bytes vector
    fn get_bytes_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<u8>, f: &mut F) {
        if !self.skipuntil_bytes_fn(f) {
            return;
        }
        let begin_ptr = self.ptr;
        let mut ptr = self.ptr;
        loop {
            unsafe {
                ptr = ptr.add(1);
            }
            if ptr == self.end {
                self.ptr = ptr;
                vec.extend_from_slice(unsafe {
                    std::slice::from_raw_parts(begin_ptr, ptr_offset_u8(ptr, begin_ptr))
                });
                break;
            }
            if !f(unsafe { *ptr }) {
                self.ptr = ptr;
                vec.extend_from_slice(unsafe {
                    std::slice::from_raw_parts(begin_ptr, ptr_offset_u8(ptr, begin_ptr))
                });
                return;
            }
        }
        if unsafe { !self.inner_read() } {
            return;
        }
        ptr = self.ptr;
        loop {
            if !f(unsafe { *ptr }) {
                self.ptr = ptr;
                vec.extend_from_slice(unsafe {
                    std::slice::from_raw_parts(self.raw, ptr_offset_u8(ptr, self.raw))
                });
                return;
            }
            unsafe {
                ptr = ptr.add(1);
            }
            if ptr == self.end {
                self.ptr = ptr;
                vec.extend_from_slice(unsafe { std::slice::from_raw_parts(self.raw, self.len) });
                if unsafe { !self.inner_read() } {
                    return;
                }
                ptr = self.ptr;
            }
        }
    }
    fn get_ascii_chars_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<char>, f: &mut F) {
        if !self.skipuntil_bytes_fn(f) {
            return;
        }
        let begin_ptr = self.ptr;
        let mut ptr = self.ptr;
        loop {
            unsafe {
                ptr = ptr.add(1);
            }
            if ptr == self.end {
                self.ptr = ptr;
                let len = unsafe { ptr_offset_u8(ptr, begin_ptr) };
                vec.reserve(len);
                let mut p = begin_ptr;
                while p != ptr {
                    vec.push(unsafe { *p } as char);
                    p = unsafe { p.add(1) };
                }
                break;
            }
            if !f(unsafe { *ptr }) {
                self.ptr = ptr;
                let len = unsafe { ptr_offset_u8(ptr, begin_ptr) };
                vec.reserve(len);
                let mut p = begin_ptr;
                while p != ptr {
                    vec.push(unsafe { *p } as char);
                    p = unsafe { p.add(1) };
                }
                return;
            }
        }
        if unsafe { !self.inner_read() } {
            return;
        }
        ptr = self.ptr;
        loop {
            if !f(unsafe { *ptr }) {
                self.ptr = ptr;
                let len = unsafe { ptr_offset_u8(ptr, self.raw) };
                vec.reserve(len);
                let mut p = self.raw;
                while p != ptr {
                    vec.push(unsafe { *p } as char);
                    p = unsafe { p.add(1) };
                }
                return;
            }
            unsafe {
                ptr = ptr.add(1);
            }
            if ptr == self.end {
                self.ptr = ptr;
                let len = unsafe { ptr_offset_u8(ptr, self.raw) };
                vec.reserve(len);
                let mut p = self.raw;
                while p != ptr {
                    vec.push(unsafe { *p } as char);
                    p = unsafe { p.add(1) };
                }
                if unsafe { !self.inner_read() } {
                    return;
                }
                ptr = self.ptr;
            }
        }
    }
    fn get_ascii_byte(&mut self) -> Option<u8> {
        loop {
            match self.next() {
                Some(c @ b'!'..=b'~') => break Some(c),
                Some(_) => continue,
                None => break None,
            }
        }
    }
    fn get_ascii_bytes(&mut self, vec: &mut Vec<u8>) {
        self.get_bytes_fn(vec, &mut |c| (b'!'..=b'~').contains(&c))
    }
    fn get_ascii_chars(&mut self, vec: &mut Vec<char>) {
        self.get_ascii_chars_fn(vec, &mut |c| (b'!'..=b'~').contains(&c))
    }
    fn get_ascii_line_bytes(&mut self, vec: &mut Vec<u8>) {
        self.get_bytes_fn(vec, &mut |c| (b' '..=b'~').contains(&c))
    }
    fn get_ascii_line_bytes_trim(&mut self, vec: &mut Vec<u8>) {
        self.skipuntil_bytes_fn(&mut |c| (b'!'..=b'~').contains(&c));
        self.get_bytes_fn(vec, &mut |c| (b' '..=b'~').contains(&c));
        while vec.last() == Some(&b' ') {
            vec.pop();
        }
    }
    fn get_utf8_bytes(&mut self, vec: &mut Vec<u8>) {
        self.get_bytes_fn(vec, &mut |c| (b'!'..=0xf4).contains(&c))
    }
    fn get_utf8_line_bytes(&mut self, vec: &mut Vec<u8>) {
        self.get_bytes_fn(vec, &mut |c| (b' '..=0xf4).contains(&c))
    }
    fn get_utf8_line_bytes_trim(&mut self, vec: &mut Vec<u8>) {
        self.skipuntil_bytes_fn(&mut |c| (b'!'..=0xf4).contains(&c));
        self.get_bytes_fn(vec, &mut |c| (b' '..=0xf4).contains(&c));
        while vec.last() == Some(&b' ') {
            vec.pop();
        }
    }
}

Submission Info

Judge Result