Task: | Peli |
Sender: | ToukoP |
Submission time: | 2024-01-20 16:51:24 +0200 |
Language: | Rust |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | TIME LIMIT EXCEEDED | -- | 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | ACCEPTED | 0.00 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 2 | details |
Code
use std::{*}; fn check(graph: &Vec<Vec<usize>>, n: usize, _m: usize, a: usize, b: usize, x: usize) -> bool { let mut dist_o = vec![usize::MAX; n + 1]; let mut dist_e = vec![usize::MAX; n + 1]; let mut pe = vec![0; n + 1]; let mut po = vec![0; n + 1]; let mut visited_o = vec![false; n + 1]; let mut visited_e = vec![false; n + 1]; let mut qo = Vec::new(); let mut qe = Vec::new(); qe.push(a); dist_e[a] = 0; visited_e[a] = true; while !qe.is_empty() || !qo.is_empty() { if let Some(planet) = qe.pop() { visited_e[planet] = true; for c in graph[planet].iter() { if dist_e[planet] + 1 < dist_o[*c] { dist_o[*c] = dist_e[planet] + 1; po[*c] = planet; } if !visited_o[*c] { qo.push(*c); } } } if let Some(planet) = qo.pop() { visited_o[planet] = true; for c in graph[planet].iter() { if dist_o[planet] + 1 < dist_e[*c] { dist_e[*c] = dist_o[planet] + 1; pe[*c] = planet; } if !visited_e[*c] { qe.push(*c); } } } } //eprintln!("a: {a} b: {b} x: {x}"); //eprintln!("pe: {:?}", pe); //eprintln!("po: {:?}", po); //eprintln!("de: {:?}", dist_e); //eprintln!("ddo: {:?}", dist_o); //eprintln!("de: {}, do: {}", dist_e[b], dist_o[b]); if x % 2 == 0 { dist_e[b] <= x } else { dist_o[b] <= x } } fn main() { let stdin = io::stdin(); let mut str = String::new(); stdin.read_line(&mut str).unwrap(); let mut s = str.split(" "); let n: usize = s.next().unwrap().trim().parse().unwrap(); let m: usize = s.next().unwrap().trim().parse().unwrap(); let q: usize = s.next().unwrap().trim().parse().unwrap(); let mut graph = vec![vec![]; n + 1]; for _ in 0..m { let mut str = String::new(); stdin.read_line(&mut str).unwrap(); let mut s = str.split(" "); let a: usize = s.next().unwrap().trim().parse().unwrap(); let b: usize = s.next().unwrap().trim().parse().unwrap(); graph[a].push(b); graph[b].push(a); } //eprintln!("{:?}", graph); let mut res: Vec<bool> = vec![]; for _ in 0..q { let mut str = String::new(); stdin.read_line(&mut str).unwrap(); let mut s = str.split(" "); let a: usize = s.next().unwrap().trim().parse().unwrap(); let b: usize = s.next().unwrap().trim().parse().unwrap(); let x: usize = s.next().unwrap().trim().parse().unwrap(); res.push(check(&graph, n, m, a, b, x)); } println!("{}", res.into_iter() .map(|b| if b {String::from("YES")} else {String::from("NO")}) .collect::<Vec<String>>().join("\n")); }
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
2 1 100 1 2 1 1 0 1 2 0 2 1 0 ... |
correct output |
---|
YES NO NO YES NO ... |
user output |
---|
YES NO NO YES NO ... Truncated |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
50 49 100 33 34 7 8 49 50 47 48 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 3
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 2499 100000 821 822 2351 2352 752 753 832 833 ... |
correct output |
---|
NO YES YES NO NO ... |
user output |
---|
(empty) |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
12 12 100 9 10 2 3 1 12 1 2 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 5
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
11 11 100 10 11 7 8 1 2 5 6 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
NO YES YES YES YES ... Truncated |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 2500 100000 1936 1937 1884 1885 751 752 831 832 ... |
correct output |
---|
NO YES YES NO NO ... |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2499 2499 100000 821 822 2351 2352 752 753 832 833 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
(empty) |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
50 99 100 40 47 34 50 44 47 15 16 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... Truncated |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 4999 100000 1191 2361 251 399 1026 2300 82 1655 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
(empty) |
Test 10
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 4999 100000 2023 2218 23 51 1020 1272 11 114 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
(empty) |