// https://infoarena.ro/problema/sate
mod helperlib {
// `local` is a cfg set only by the local .cargo/config.toml (see setup_week.py), never by the judges
#![allow(unexpected_cfgs)]
use std::{fs::*, io::*, path::*};
pub trait ReadFromReader {
fn read<R: BufRead>(reader: &mut R) -> Result<Self> where Self: Sized;
}
macro_rules! impl_num_read {
($($typ: ty)*) => {$(
impl ReadFromReader for $typ {
fn read<R: BufRead>(reader: &mut R) -> Result<Self> {
let mut res = None;
let minus = Some(b'-') == reader.fill_buf()?.first().copied();
if minus {
if Self::MIN == 0 {
let err = format!("Could not parse negative number as {}.", std::any::type_name::<Self>());
return Err(std::io::Error::new(ErrorKind::InvalidData, err));
}
reader.consume(1);
}
loop {
let b = match reader.fill_buf()?.first() {
Some(&b) => b,
None => break,
};
if b.is_ascii_digit() {
reader.consume(1);
let b = b as Self;
if let Some(res) = res.as_mut() {
*res *= 10;
if minus {
*res -= b - b'0' as Self;
} else {
*res += b - b'0' as Self;
}
} else {
if minus {
res = Some(b'0' as Self - b);
} else {
res = Some(b - b'0' as Self);
}
}
} else {
break;
}
}
if let Some(res) = res {
Ok(res)
} else {
let err = format!("Could not parse type {}.", std::any::type_name::<Self>());
Err(std::io::Error::new(ErrorKind::InvalidData, err))
}
}
}
)*};
}
impl_num_read!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
impl ReadFromReader for char {
fn read<R: BufRead>(reader: &mut R) -> Result<Self> {
let invalid = || std::io::Error::new(ErrorKind::InvalidData, "Invalid UTF-8 sequence.");
let mut buf = [0u8; 4];
reader.read_exact(&mut buf[..1]).map_err(|e| {
if e.kind() == ErrorKind::UnexpectedEof {
std::io::Error::new(ErrorKind::UnexpectedEof, "Could not read char: end of input.")
} else {
e
}
})?;
let len = match buf[0] {
0x00..=0x7F => 1,
0xC0..=0xDF => 2,
0xE0..=0xEF => 3,
0xF0..=0xF7 => 4,
_ => return Err(invalid()),
};
reader.read_exact(&mut buf[1..len])?;
std::str::from_utf8(&buf[..len])
.map_err(|_| invalid())?
.chars()
.next()
.ok_or_else(invalid)
}
}
impl ReadFromReader for String {
// reads from the current position up to (not including) the next whitespace
fn read<R: BufRead>(reader: &mut R) -> Result<Self> {
let mut bytes = Vec::new();
loop {
let buf = reader.fill_buf()?;
if buf.is_empty() {
break;
}
let len = buf.iter().position(|b| b.is_ascii_whitespace()).unwrap_or(buf.len());
bytes.extend_from_slice(&buf[..len]);
let done = len < buf.len();
reader.consume(len);
if done {
break;
}
}
if bytes.is_empty() {
return Err(std::io::Error::new(ErrorKind::UnexpectedEof, "Could not read String: no characters before whitespace or end of input."));
}
String::from_utf8(bytes).map_err(|_| std::io::Error::new(ErrorKind::InvalidData, "Invalid UTF-8 sequence."))
}
}
pub struct Reader<R> {
reader: BufReader<R>,
// true right after a token was read: the rest of its line (e.g. the trailing newline) is still unread
mid_line: bool,
}
impl Reader<File> {
#[allow(dead_code)]
pub fn new(path: impl AsRef<Path>) -> Result<Self> {
Ok(Self::from_reader(File::open(path)?))
}
}
impl Reader<Stdin> {
#[allow(dead_code)]
pub fn new_stdin() -> Self {
Self::from_reader(stdin())
}
}
impl<R: Read> Reader<R> {
pub fn from_reader(reader: R) -> Self {
Reader { reader: BufReader::new(reader), mid_line: false }
}
#[allow(dead_code)]
pub fn read_unspaced<T: ReadFromReader>(&mut self) -> Result<T> {
T::read(&mut self.reader)
}
#[allow(dead_code)]
pub fn read_whitespaced<T: ReadFromReader>(&mut self) -> Result<T> {
while matches!(self.reader.fill_buf()?.first(), Some(b) if b.is_ascii_whitespace()) { self.reader.consume(1); }
let res = T::read(&mut self.reader);
self.mid_line = res.is_ok();
res
}
#[allow(dead_code)]
pub fn read_line_of<T: ReadFromReader>(&mut self) -> impl Iterator<Item = T> + '_ {
// finish the line of the previous token, so its newline doesn't end this (next) line immediately
if std::mem::take(&mut self.mid_line) {
while let Some(&b) = self.reader.fill_buf().ok().and_then(|buf| buf.first()) {
if !b.is_ascii_whitespace() { break; }
self.reader.consume(1);
if b == b'\n' { break; }
}
}
std::iter::from_fn(move || {
loop {
let &b = self.reader.fill_buf().ok()?.first()?;
if b.is_ascii_whitespace() {
self.reader.consume(1);
if b == b'\n' {
self.mid_line = false;
return None;
}
} else {
// if the caller stops after this item, the rest of its line is still unread
let item = T::read(&mut self.reader).ok();
self.mid_line = item.is_some();
return item;
}
}
})
}
}
pub trait WriteToWriter {
fn write<W: Write>(&self, writer: &mut W) -> Result<()>;
}
macro_rules! impl_num_write {
($($typ: ty)*) => {$(
impl WriteToWriter for $typ {
fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
if *self == 0 {
writer.write_all(b"0")
} else {
const BUF_LEN: usize = 128;
let mut buf = [0; BUF_LEN];
let mut buf_index = BUF_LEN - 1;
let mut copy = *self;
while copy != 0 {
buf[buf_index] = b'0' + ((copy % 10) as i8).unsigned_abs();
copy /= 10;
buf_index -= 1;
}
#[allow(unused_comparisons)]
if *self < 0 {
buf[buf_index] = b'-';
} else {
buf_index += 1;
}
writer.write_all(&buf[buf_index..])
}
}
}
)*};
}
impl_num_write!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
impl WriteToWriter for char {
fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
let mut buf = [0u8; 4]; // the longest UTF-8 encoding of a char
self.encode_utf8(&mut buf);
writer.write_all(&buf[..self.len_utf8()])
}
}
impl WriteToWriter for str {
fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
writer.write_all(self.as_bytes())
}
}
impl WriteToWriter for String {
fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
self.as_str().write(writer)
}
}
// lets `&str` (and any other reference) be passed where a `T: WriteToWriter` is expected
impl<T: WriteToWriter + ?Sized> WriteToWriter for &T {
fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
(**self).write(writer)
}
}
pub struct Writer<W: Write> {
writer: BufWriter<W>
}
impl Writer<File> {
#[allow(dead_code)]
pub fn new(path: impl AsRef<Path>) -> Result<Self> {
Ok(Self::from_writer(File::create(path)?))
}
}
impl Writer<Stdout> {
#[allow(dead_code)]
pub fn new_stdout() -> Self {
Self::from_writer(stdout())
}
}
impl<W: Write> Writer<W> {
#[allow(dead_code)]
pub fn from_writer(writer: W) -> Self {
Writer { writer: BufWriter::new(writer) }
}
#[allow(dead_code)]
pub fn flush(&mut self) -> Result<()> {
self.writer.flush()
}
// flushes, then gives back the underlying writer
#[allow(dead_code)]
pub fn into_inner(self) -> Result<W> {
self.writer.into_inner().map_err(|e| e.into_error())
}
#[allow(dead_code)]
pub fn write_unspaced<T: WriteToWriter + ?Sized>(&mut self, val: &T) -> Result<()> {
val.write(&mut self.writer)
}
#[allow(dead_code)]
pub fn write_spaced<T: WriteToWriter + ?Sized>(&mut self, val: &T) -> Result<()> {
val.write(&mut self.writer)?;
' '.write(&mut self.writer)
}
// items separated by single spaces, then a newline (no trailing space)
#[allow(dead_code)]
pub fn write_iter_spaced_newlined<T: WriteToWriter, I: IntoIterator<Item = T>>(&mut self, iter: I) -> Result<()> {
for (i, item) in iter.into_iter().enumerate() {
if i > 0 {
' '.write(&mut self.writer)?;
}
item.write(&mut self.writer)?;
}
'\n'.write(&mut self.writer)
}
#[allow(dead_code)]
pub fn write_line<T: WriteToWriter + ?Sized>(&mut self, val: &T) -> Result<()> {
val.write(&mut self.writer)?;
'\n'.write(&mut self.writer)
}
}
// Runs the problem's `solve(reader, writer)`, which lives in main.rs: once this file is inlined as
// `mod helperlib`, `crate::solve` is that function.
// stand-in so this file also compiles on its own
#[allow(dead_code)]
fn solve<R: Read, W: Write>(_reader: &mut Reader<R>, _writer: &mut Writer<W>) {}
#[allow(dead_code)]
fn run_on_console() {
let mut reader = Reader::new_stdin();
let mut writer = Writer::new_stdout();
crate::solve(&mut reader, &mut writer);
writer.flush().unwrap();
}
/// Locally: runs `solve` on every `<name>.in`, `<name>_2.in`, ... next to Cargo.toml and compares with
/// the matching `.ex_out`. Judges: runs it once on the files `<name>.in` / `<name>.out`.
#[allow(dead_code)]
pub fn run_tests(name: &str) {
#[cfg(local)]
test_locally(name);
#[cfg(not(local))]
{
let mut reader = Reader::new(format!("{name}.in")).unwrap();
let mut writer = Writer::new(format!("{name}.out")).unwrap();
crate::solve(&mut reader, &mut writer);
writer.flush().unwrap();
}
}
/// Same as `run_tests` locally; judges: runs `solve` once on stdin / stdout.
#[allow(dead_code)]
pub fn run_tests_console(name: &str) {
#[cfg(local)]
test_locally(name);
#[cfg(not(local))]
{
let _ = name;
run_on_console();
}
}
/// First line (1-based) where the outputs differ, ignoring whitespace at the end of each line.
#[cfg(local)]
fn first_difference(expected: &str, actual: &str) -> Option<(usize, String, String)> {
let mut expected = expected.lines().map(str::trim_end);
let mut actual = actual.lines().map(str::trim_end);
for line in 1.. {
match (expected.next(), actual.next()) {
(None, None) => return None,
(e, a) if e == a => {}
(e, a) => {
let show = |l: Option<&str>| l.unwrap_or("<end of output>").to_string();
return Some((line, show(e), show(a)));
}
}
}
unreachable!()
}
#[cfg(local)]
fn test_locally(name: &str) {
let dir = Path::new(env!("CARGO_MANIFEST_DIR"));
// (number, file name): <name>.in is test 1, <name>_N.in is test N
let mut tests: Vec<(usize, String)> = Vec::new();
for entry in read_dir(dir).into_iter().flatten().flatten() {
let file = entry.file_name().to_string_lossy().into_owned();
let Some(stem) = file.strip_suffix(".in") else { continue };
let number = if stem == name {
1
} else if let Some(n) = stem.strip_prefix(name).and_then(|r| r.strip_prefix('_')).and_then(|n| n.parse().ok()) {
n
} else {
continue;
};
tests.push((number, file));
}
tests.sort();
if tests.is_empty() {
println!("No test files for `{name}` found; reading from the console.");
return run_on_console();
}
for (_, file) in tests {
let expected_file = format!("{}.ex_out", file.strip_suffix(".in").unwrap());
let run = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| -> Result<Vec<u8>> {
let mut reader = Reader::from_reader(File::open(dir.join(&file))?);
let mut writer = Writer::from_writer(Vec::new());
crate::solve(&mut reader, &mut writer);
writer.into_inner()
}));
let output = match run {
Ok(Ok(output)) => String::from_utf8_lossy(&output).into_owned(),
Ok(Err(e)) => {
println!("Test {file} could not run: {e}.");
continue;
}
Err(payload) => {
let message = payload.downcast_ref::<&str>().map(|s| s.to_string())
.or_else(|| payload.downcast_ref::<String>().cloned())
.unwrap_or_else(|| "unknown panic".to_string());
println!("Test {file} panicked: {message}");
continue;
}
};
match std::fs::read_to_string(dir.join(&expected_file)) {
Err(_) => println!("Test {file} ran, but there is no {expected_file} to compare with."),
Ok(expected) => match first_difference(&expected, &output) {
None => println!("Test {file} passed successfully."),
Some((line, e, a)) => println!("Test {file} differs at line {line}: expected `{e}`, got `{a}`."),
},
}
}
}
}
use helperlib::*;
fn solve<R: std::io::Read, W: std::io::Write>(reader: &mut Reader<R>, writer: &mut Writer<W>) {
let noduri = reader.read_whitespaced().unwrap();
let muchii = reader.read_whitespaced().unwrap();
let x: usize = reader.read_whitespaced().unwrap();
let y: usize = reader.read_whitespaced().unwrap();
let mut adiacente = vec![Vec::new(); noduri];
for _ in 0..muchii {
let muchie1: usize = reader.read_whitespaced().unwrap();
let muchie2: usize = reader.read_whitespaced().unwrap();
let distanta: usize = reader.read_whitespaced().unwrap();
adiacente[muchie1 - 1].push((muchie2 - 1, distanta));
adiacente[muchie2 - 1].push((muchie1 - 1, distanta));
}
let mut coord_relativ_current = vec![None; noduri];
coord_relativ_current[x - 1] = Some(0isize);
let mut frontiera_current = vec![x - 1];
let mut coord_relativ_other = vec![None; noduri];
coord_relativ_other[y - 1] = Some(0isize);
let mut frontiera_other = vec![y - 1];
loop {
let mut noua_frontiera = vec![];
for ¤t in &frontiera_current {
for &(adiacent, distanta_current_adiacent) in &adiacente[current] {
let coord_relativ = coord_relativ_current[current].unwrap() +
if adiacent < current { -(distanta_current_adiacent as isize) }
else { distanta_current_adiacent as isize };
if coord_relativ_current[adiacent].is_some() {
continue;
}
if let Some(coord_relativ_other) = coord_relativ_other[adiacent] {
writer.write_line(&(coord_relativ - coord_relativ_other).abs()).unwrap();
return;
}
noua_frontiera.push(adiacent);
coord_relativ_current[adiacent] = Some(coord_relativ);
}
}
frontiera_current = noua_frontiera;
std::mem::swap(&mut coord_relativ_current, &mut coord_relativ_other);
std::mem::swap(&mut frontiera_current, &mut frontiera_other);
}
}
fn main() {
run_tests("sate");
}
Dav Abc David_92