QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#273185#7883. Takeout Deliveringucup-team635#ML 0ms2100kbRust6.0kb2023-12-02 21:54:132023-12-02 21:54:15

Judging History

你现在查看的是最新测评结果

  • [2023-12-02 21:54:15]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:2100kb
  • [2023-12-02 21:54:13]
  • 提交

answer

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    input! {
        n: usize,
        m: usize,
        e: [(usize1, usize1, i64); m],
    }
    let mut e = e;
    for e in e.iter_mut() {
        *e = (e.0.min(e.1), e.0.max(e.1), e.2);
    }
    e.sort_by_key(|e| e.2);
    let mut g = vec![vec![]; n];
    for &(a, b, c) in e.iter() {
        g[a].push((a, b, c));
        g[b].push((a, b, c));
    }
    let mut dp = vec![false; n];
    let mut ep = vec![false; n];
    dp[0] = true;
    ep[n - 1] = true;
    let mut dsu = DSU::new(n);
    let mut tree = vec![vec![]; n];
    let inf = std::i64::MAX / 3;
    let mut val = inf;
    let mut ans = inf;
    for (a, b, c) in e {
        if (a, b) == (0, n - 1) {
            ans.chmin(c);
        }
        if let Some((p, ch)) = dsu.unite(a, b) {
            tree[a].push((b, c));
            tree[b].push((a, c));
            if dp[p] != dp[ch] || ep[p] != ep[ch] {
                for &r in [p, ch].iter() {
                    if (!dp[r] && dp[r ^ p ^ ch]) || (!ep[r] && ep[r ^ p ^ ch]) {
                        for &(a, b, w) in g[r].iter() {
                            let mut p = [dsu.root(0), dsu.root(n - 1)];
                            let mut q = [dsu.root(a), dsu.root(b)];
                            p.sort();
                            q.sort();
                            if p[0] != p[1] && p == q {
                                val.chmin(w);
                            }
                        }
                    }
                }
            }
            dp[p] |= dp[ch];
            ep[p] |= ep[ch];
            let mut x = std::mem::take(&mut g[ch]);
            g[p].append(&mut x);
        }
        ans.chmin(c + val);
    }
    /*
    let mut dfs = vec![0];
    let mut parent = vec![(n, 0); n];
    parent[0].0 = 0;
    while let Some(v) = dfs.pop() {
        for &(u, w) in tree[v].iter() {
            if parent[u].0 == n {
                parent[u] = (v, w);
                dfs.push(u);
            }
        }
    }
    let mut a = vec![];
    let mut pos = n - 1;
    while pos != 0 {
        let p = parent[pos];
        a.push(p.1);
        pos = p.0;
    }
    a.sort();
    ans.chmin(a.iter().rev().take(2).sum::<i64>());
    */
    println!("{}", ans);
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
//---------- begin union_find ----------
pub struct DSU {
    p: Vec<i32>,
}
impl DSU {
    pub fn new(n: usize) -> DSU {
        assert!(n < std::i32::MAX as usize);
        DSU { p: vec![-1; n] }
    }
    pub fn init(&mut self) {
        self.p.iter_mut().for_each(|p| *p = -1);
    }
    pub fn root(&self, mut x: usize) -> usize {
        assert!(x < self.p.len());
        while self.p[x] >= 0 {
            x = self.p[x] as usize;
        }
        x
    }
    pub fn same(&self, x: usize, y: usize) -> bool {
        assert!(x < self.p.len() && y < self.p.len());
        self.root(x) == self.root(y)
    }
    pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
        assert!(x < self.p.len() && y < self.p.len());
        let mut x = self.root(x);
        let mut y = self.root(y);
        if x == y {
            return None;
        }
        if self.p[x] > self.p[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.p[x] += self.p[y];
        self.p[y] = x as i32;
        Some((x, y))
    }
    pub fn parent(&self, x: usize) -> Option<usize> {
        assert!(x < self.p.len());
        let p = self.p[x];
        if p >= 0 {
            Some(p as usize)
        } else {
            None
        }
    }
    pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
    where
        F: FnMut(usize),
    {
        while let Some(p) = self.parent(x) {
            f(x);
            x = p;
        }
        x
    }
    pub fn size(&self, x: usize) -> usize {
        assert!(x < self.p.len());
        let r = self.root(x);
        (-self.p[r]) as usize
    }
}
//---------- end union_find ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}
// ---------- end chmin, chmax ----------

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 2100kb

input:

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: -100
Memory Limit Exceeded

input:

300000 299999
80516 80517 597830404
110190 110191 82173886
218008 218009 954561262
250110 250111 942489774
66540 66541 156425292
34947 34948 239499776
273789 273790 453201232
84428 84429 439418398
98599 98600 326095035
55636 55637 355015760
158611 158612 684292473
43331 43332 43265001
171621 171622 ...

output:

1999991697

result: