結果
| 問題 | No.3616 WK vs AT vs MT vs SP |
| コンテスト | |
| ユーザー |
 elphe
|
| 提出日時 | 2026-08-06 16:04:21 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 161 ms / 2,000 ms |
| + 175µs | |
| コード長 | 21,459 bytes |
| 記録 | |
| コンパイル時間 | 8,827 ms |
| コンパイル使用メモリ | 199,976 KB |
| 実行使用メモリ | 53,524 KB |
| 最終ジャッジ日時 | 2026-08-06 16:04:37 |
| 合計ジャッジ時間 | 11,589 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 1 |
| 小課題1 | 8 % | AC * 9 |
| 小課題2 | 16 % | AC * 5 |
| 小課題3 | 20 % | AC * 10 |
| 小課題4 | 20 % | AC * 15 |
| 小課題5 | 20 % | AC * 15 |
| 小課題6 | 16 % | AC * 36 |
| 合計 | 2.5 * 100% = 250 点 |
ソースコード
fn main() {
let stdin = std::io::read_to_string(std::io::stdin().lock()).unwrap();
let mut stdin = stdin.split_ascii_whitespace();
unsafe {
read!(stdin -> (n: u16, r: u16, c: u64, x: Vec[u32; n], y: Vec[u32; n], z: Vec[u32; n], s: Vec[u32; n], edges: Vec[(u32, u32, u32, u32, u32); r]));
write!(output(solve(c, x, y, z, s, edges)));
}
}
fn solve(
c: u64,
x: Vec<u32>,
y: Vec<u32>,
z: Vec<u32>,
s: Vec<u32>,
edges: Vec<(u32, u32, u32, u32, u32)>,
) -> u64 {
let n = s.len();
let mut next_of = vec![Vec::new(); (n + 1) << 3];
next_of
.chunks_exact_mut(1 << 3)
.enumerate()
.skip(1)
.zip(x)
.for_each(|((i, next_of), x)| {
next_of
.iter_mut()
.enumerate()
.filter(|&(j, _)| j & 1 == 0)
.for_each(|(j, nexts)| nexts.push((((i << 3) | j | 1) as u32, x as u64)));
});
next_of
.chunks_exact_mut(1 << 3)
.enumerate()
.skip(1)
.zip(y)
.for_each(|((i, next_of), y)| {
next_of
.iter_mut()
.enumerate()
.filter(|&(j, _)| j & 2 == 0)
.for_each(|(j, nexts)| nexts.push((((i << 3) | j | 2) as u32, y as u64)));
});
next_of
.chunks_exact_mut(1 << 3)
.enumerate()
.skip(1)
.zip(z)
.for_each(|((i, next_of), z)| {
next_of
.iter_mut()
.enumerate()
.filter(|&(j, _)| j & 4 == 0)
.for_each(|(j, nexts)| nexts.push((((i << 3) | j | 4) as u32, z as u64)));
});
next_of
.chunks_exact_mut(1 << 3)
.skip(1)
.zip(s.iter())
.for_each(|(next_of, &s)| {
next_of
.iter_mut()
.enumerate()
.filter(|&(j, _)| j & 4 != 0)
.for_each(|(j, nexts)| nexts.push((j as u32, s as u64 + c)));
});
s.into_iter().enumerate().for_each(|(i, s)| {
next_of
.iter_mut()
.enumerate()
.take(1 << 3)
.filter(|&(j, _)| j & 4 != 0)
.for_each(|(j, nexts)| {
nexts.push(((((i + 1) << 3) | j) as u32, s as u64));
});
});
edges.into_iter().for_each(|(u, v, w, a, m)| {
next_of
.iter_mut()
.skip((u as usize) << 3)
.take(1 << 3)
.enumerate()
.for_each(|(j, nexts)| {
if j & 2 != 0 {
nexts.push(((v << 3) | j as u32, w.min(a).min(m) as u64));
} else if j & 1 != 0 {
nexts.push(((v << 3) | j as u32, w.min(a) as u64));
} else {
nexts.push(((v << 3) | j as u32, w as u64));
}
});
next_of
.iter_mut()
.skip((v as usize) << 3)
.take(1 << 3)
.enumerate()
.for_each(|(j, nexts)| {
if j & 2 != 0 {
nexts.push((((u << 3) | j as u32), w.min(a).min(m) as u64));
} else if j & 1 != 0 {
nexts.push(((u << 3) | j as u32, w.min(a) as u64));
} else {
nexts.push(((u << 3) | j as u32, w as u64));
}
})
});
let dist = mylib::dijkstra(next_of, [1 << 3].into_iter(), 0, u64::MAX);
dist.into_iter().skip(n << 3).take(1 << 3).min().unwrap()
}
fn output(ans: u64) -> String {
format!("{}", ans)
}
mod mylib {
pub fn dijkstra<T: Clone, U: Clone + Ord + From<T> + std::ops::Add<Output = U>>(
next_of: Vec<Vec<(u32, T)>>,
starts: impl Iterator<Item = u32>,
zero_cost: U,
max_cost: U,
) -> Vec<U> {
use std::cmp::Reverse;
let mut dist = vec![max_cost; next_of.len()];
let mut pq = starts
.inspect(|&start| dist[start as usize] = zero_cost.clone())
.map(|start| Reverse((zero_cost.clone(), start)))
.collect::<std::collections::BinaryHeap<_>>();
while let Some(Reverse((cur_dist, cur_pos))) = pq.pop() {
if cur_dist == dist[cur_pos as usize] {
next_of[cur_pos as usize].iter().for_each(|(next, cost)| {
if dist[*next as usize] > cur_dist.clone() + cost.clone().into() {
dist[*next as usize] = cur_dist.clone() + cost.clone().into();
pq.push(Reverse((cur_dist.clone() + cost.clone().into(), *next)));
}
})
}
}
dist
}
}
#[macro_export]
macro_rules! read {
($iter:ident -> ($v:ident : $t1:tt $([$($t2:tt)+] $({$($t3:tt)+})?)?)) => {
let $v = read_value!($iter -> $t1 $([$($t2)+] $({$($t3)+})? )?);
};
($iter:ident -> ($v:ident : $t1:tt $([$($t2:tt)+] $({$($t3:tt)+})?)? , $($r:tt)*)) => {
read!($iter -> ($v : $t1 $([$($t2)+] $({$($t3)+})?)?));
read!($iter -> ($($r)*));
};
}
#[macro_export]
macro_rules! read_value {
($source:ident -> ($($t1:tt $([$($t2:tt)+])?),+)) => {
( $(read_value!($source -> $t1 $([$($t2)+])?)),* )
};
($source:ident -> [ $t1:tt ; $len:expr ]) => {
{
let mut x: [::std::mem::MaybeUninit<$t1>; $len] = ::std::mem::MaybeUninit::uninit().assume_init();
for elem in x.iter_mut() {
elem.as_mut_ptr().write(read_value!($source -> $t1));
}
::std::mem::transmute::<[::std::mem::MaybeUninit<$t1>; $len], [$t1; $len]>(x)
}
};
($source:ident -> [ $c2:tt [ $t1:tt $(; $len2:expr)? ] ; $len1:expr ]) => {
{
let mut x: [::std::mem::MaybeUninit<$c2<$t1>>; $len1] = unsafe { ::std::mem::MaybeUninit::uninit().assume_init() };
for elem in x.iter_mut() {
elem.as_mut_ptr().write(read_value!($source -> $c2 [ $t1 $(; $len2)? ]));
}
::std::mem::transmute::<[::std::mem::MaybeUninit<$c2<$t1>>; $len1], [$c2<$t1>; $len1]>(x)
}
};
($source:ident -> $t1:tt[ $t2:tt $([$($t3:tt)+])? ; $len:expr ]) => {
(0..($len)).map(|_| read_value!($source -> $t2 $([$($t3)+])?)).collect::<$t1<_>>()
};
($source:ident -> $t1:tt[ $t2:tt $([$($t3:tt)+])? ]) => {
(0..(read_value!($source -> u32))).map(|_| read_value!($source -> $t2 $([$($t3)+])?)).collect::<$t1<_>>()
};
($source:ident -> $t1:tt[ ($($t2:tt),+) ; $len:expr ] { $($p1:pat => ($($pos:tt),*)),* }) => {
(0..($len)).map(|_| {
let mut v = ($($t2::default()),+);
v.0 = my_parser::parse_without_checking(($source).next().unwrap());
match v.0 {
$($p1 => {
$(v.$pos = my_parser::parse_without_checking(($source).next().unwrap()));*
}),*
_ => unreachable!(),
}
v
}).collect::<$t1<_>>()
};
($source:ident -> $t1:tt[ ($($t2:tt),+) ] { $($p1:pat => ($($pos:tt),*)),* }) => {
read_value!($source -> $t1[ ($($t2),+) ; read_value!($source -> u32) ] { $($p1 => ($($pos),*)),* })
};
($source:ident -> $t:ty) => {
my_parser::parse_without_checking::<$t>(($source).next().unwrap())
};
}
mod my_parser {
#[allow(unused)]
pub unsafe fn parse_without_checking<F: std::str::FromStr + Parsable>(target: &str) -> F {
unsafe { Parsable::from_str(target) }
}
pub trait Parsable {
unsafe fn from_str(s: &str) -> Self;
}
impl Parsable for String {
unsafe fn from_str(s: &str) -> Self {
Self::from(s)
}
}
impl Parsable for char {
unsafe fn from_str(s: &str) -> Self {
s.chars().next().unwrap()
}
}
macro_rules! parse_float {
($s:ident) => {{
let mut iter = $s.bytes().peekable();
let sign = match iter.peek().unwrap() {
b'-' => {
iter.next();
-1.0
}
b'+' => {
iter.next();
1.0
}
_ => 1.0,
};
let mut result = 0.0;
while let Some(cur) = iter.next()
&& cur != b'.'
{
result = result * 10.0 + (cur - b'0') as Self;
}
let mut digit = 1.0;
(result
+ iter
.map(|cur| {
digit *= 0.1;
digit * (cur - b'0') as Self
})
.sum::<Self>())
* sign
}};
}
impl Parsable for u8 {
unsafe fn from_str(s: &str) -> Self {
((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u32)) & 0x0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16) as Self
}
}
impl Parsable for u16 {
unsafe fn from_str(s: &str) -> Self {
((((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u64)) & 0x0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32) as Self
}
}
impl Parsable for u32 {
unsafe fn from_str(s: &str) -> Self {
((((((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u128))
& 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32)
& 0x00000000ffffffff00000000ffffffff)
.wrapping_mul((1 << 64) + 100000000)
>> 64) as Self
}
}
impl Parsable for u64 {
unsafe fn from_str(s: &str) -> Self {
const POW_10: [u64; 17] = [
1,
10,
100,
1_000,
10_000,
100_000,
1_000_000,
10_000_000,
100_000_000,
1_000_000_000,
10_000_000_000,
100_000_000_000,
1_000_000_000_000,
10_000_000_000_000,
100_000_000_000_000,
1_000_000_000_000_000,
10_000_000_000_000_000,
];
s.as_bytes().chunks(16).fold(0, |acc, x| {
acc * POW_10[x.len()]
+ ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
& 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32)
& 0x00000000ffffffff00000000ffffffff)
.wrapping_mul((1 << 64) + 100000000)
>> 64) as Self
})
}
}
impl Parsable for u128 {
unsafe fn from_str(s: &str) -> Self {
const POW_10: [u128; 17] = [
1,
10,
100,
1_000,
10_000,
100_000,
1_000_000,
10_000_000,
100_000_000,
1_000_000_000,
10_000_000_000,
100_000_000_000,
1_000_000_000_000,
10_000_000_000_000,
100_000_000_000_000,
1_000_000_000_000_000,
10_000_000_000_000_000,
];
s.as_bytes().chunks(16).fold(0, |acc, x| {
acc * POW_10[x.len()]
+ ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
& 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32)
& 0x00000000ffffffff00000000ffffffff)
.wrapping_mul((1 << 64) + 100000000)
>> 64) as Self
})
}
}
impl Parsable for i8 {
unsafe fn from_str(s: &str) -> Self {
((((((s
.bytes()
.skip(match s.as_bytes()[0].is_ascii_digit() {
true => 0,
false => 1,
})
.fold(0, |acc, x| (acc << 8) | (x as u32))
& 0x0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16) as i32)
* match s.as_bytes()[0] == b'-' {
true => -1,
false => 1,
}) as Self
}
}
impl Parsable for i16 {
unsafe fn from_str(s: &str) -> Self {
((((((((s
.bytes()
.skip(match s.as_bytes()[0].is_ascii_digit() {
true => 0,
false => 1,
})
.fold(0, |acc, x| (acc << 8) | (x as u64))
& 0x0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32) as i64)
* match s.as_bytes()[0] == b'-' {
true => -1,
false => 1,
}) as Self
}
}
impl Parsable for i32 {
unsafe fn from_str(s: &str) -> Self {
((((((((((s
.bytes()
.skip(match s.as_bytes()[0].is_ascii_digit() {
true => 0,
false => 1,
})
.fold(0, |acc, x| (acc << 8) | (x as u128))
& 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32)
& 0x00000000ffffffff00000000ffffffff)
.wrapping_mul((1 << 64) + 100000000)
>> 64) as i128)
* match s.as_bytes()[0] == b'-' {
true => -1,
false => 1,
}) as Self
}
}
impl Parsable for i64 {
unsafe fn from_str(s: &str) -> Self {
const POW_10: [u64; 17] = [
1,
10,
100,
1_000,
10_000,
100_000,
1_000_000,
10_000_000,
100_000_000,
1_000_000_000,
10_000_000_000,
100_000_000_000,
1_000_000_000_000,
10_000_000_000_000,
100_000_000_000_000,
1_000_000_000_000_000,
10_000_000_000_000_000,
];
let skip = match s.as_bytes()[0].is_ascii_digit() {
true => 0,
false => 1,
};
((s.as_bytes()[skip..].chunks(16).fold(0, |acc, x| {
acc * POW_10[x.len()]
+ ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
& 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32)
& 0x00000000ffffffff00000000ffffffff)
.wrapping_mul((1 << 64) + 100000000)
>> 64) as u64
}) as i64)
* match s.as_bytes()[0] == b'-' {
true => -1,
false => 1,
}) as Self
}
}
impl Parsable for i128 {
unsafe fn from_str(s: &str) -> Self {
const POW_10: [u128; 17] = [
1,
10,
100,
1_000,
10_000,
100_000,
1_000_000,
10_000_000,
100_000_000,
1_000_000_000,
10_000_000_000,
100_000_000_000,
1_000_000_000_000,
10_000_000_000_000,
100_000_000_000_000,
1_000_000_000_000_000,
10_000_000_000_000_000,
];
let skip = match s.as_bytes()[0].is_ascii_digit() {
true => 0,
false => 1,
};
((s.as_bytes()[skip..].chunks(16).fold(0, |acc, x| {
acc * POW_10[x.len()]
+ ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
& 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
.wrapping_mul((1 << 8) + 10)
>> 8)
& 0x00ff00ff00ff00ff00ff00ff00ff00ff)
.wrapping_mul((1 << 16) + 100)
>> 16)
& 0x0000ffff0000ffff0000ffff0000ffff)
.wrapping_mul((1 << 32) + 10000)
>> 32)
& 0x00000000ffffffff00000000ffffffff)
.wrapping_mul((1 << 64) + 100000000)
>> 64)
}) as i128)
* match s.as_bytes()[0] == b'-' {
true => -1,
false => 1,
}) as Self
}
}
impl Parsable for f32 {
unsafe fn from_str(s: &str) -> Self {
parse_float!(s)
}
}
impl Parsable for f64 {
unsafe fn from_str(s: &str) -> Self {
parse_float!(s)
}
}
}
#[macro_export]
macro_rules! write {
($out:expr) => {{
use std::io::Write;
std::io::stdout()
.lock()
.write_all(($out).as_bytes())
.unwrap();
}};
}
#[macro_export]
macro_rules! format_iter {
($i:expr, $sep:expr, ($($elem:ident),+) -> ($form:expr $(, $ex:expr)*)) => {{
#[allow(unused_parens)]
let ($($elem),+) = i.next().unwrap();
#[allow(unused_parens)]
$i.fold(std::format!($form $(, $ex)*), |mut acc, ($($elem),+)| {
use std::fmt::Write;
acc.push_str($sep);
std::write!(&mut acc, $form $(, $ex)*).unwrap();
acc
})
}}
}
#[macro_export]
macro_rules! format_vec {
($v:expr, $sep:expr, ($($elem:ident),+) -> ($form:expr $(, $ex:expr)*)) => {{
if $v.is_empty() {
String::new()
} else {
let mut v = $v;
#[allow(unused_parens)]
let ($($elem),+) = v.drain(..1).next().unwrap();
#[allow(unused_parens)]
v.into_iter().fold(std::format!($form $(, $ex)*), |mut acc, ($($elem),+)| {
use std::fmt::Write;
acc.push_str($sep);
std::write!(&mut acc, $form $(, $ex)*).unwrap();
acc
})
}
}}
}
#[macro_export]
macro_rules! format_vec_vec {
($v:expr, $sep1:expr, $sep2:expr, ($($elem:ident),+) -> ($form:expr $(, $ex:expr)*)) => {{
let mut v = $v;
let v_first = v.drain(..1).next().unwrap();
#[allow(unused_parens)]
v.into_iter().fold(format_vec!(v_first, $sep2, ($($elem),+) -> ($form $(, $ex)*)), |mut acc, mut v| {
use std::fmt::Write;
acc.push_str($sep1);
let ($($elem),+) = v.drain(..1).next().unwrap();
std::write!(&mut acc, $form $(, $ex)*).unwrap();
v.into_iter().fold(acc, |mut acc, ($($elem),+)| {
acc.push_str($sep2);
std::write!(&mut acc, $form $(, $ex)*).unwrap();
acc
})
})
}}
}