| Task: | Hypyt |
| Sender: | asonnine |
| Submission time: | 2025-11-06 16:03:15 +0200 |
| Language: | Rust (2021) |
| Status: | READY |
| Result: | 30 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 10 |
| #2 | ACCEPTED | 20 |
| #3 | TIME LIMIT EXCEEDED | 0 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| #5 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #2 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #3 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #4 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #5 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #6 | ACCEPTED | 0.26 s | 2, 5 | details |
| #7 | ACCEPTED | 0.28 s | 2, 5 | details |
| #8 | ACCEPTED | 0.19 s | 2, 5 | details |
| #9 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
| #10 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
| #11 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
| #12 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #13 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #14 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #15 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #16 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #17 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #18 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #19 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #20 | RUNTIME ERROR | 0.05 s | 5 | details |
| #21 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #22 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #23 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #24 | WRONG ANSWER | 0.32 s | 5 | details |
| #25 | ACCEPTED | 0.32 s | 5 | details |
| #26 | WRONG ANSWER | 0.34 s | 5 | details |
| #27 | ACCEPTED | 0.32 s | 5 | details |
Code
use std::{io, usize, vec};
#[derive(Debug, Clone, PartialEq, Eq)]
struct Row {
connections: Vec<usize>,
}
fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let (n, m, q): (usize, usize, usize) = {
let mut iter = input.split_whitespace();
(
iter.next().unwrap().parse().unwrap(),
iter.next().unwrap().parse().unwrap(),
iter.next().unwrap().parse().unwrap(),
)
};
let mut map: Vec<Vec<bool>> = Vec::new();
for _ in 0..n {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
map.push(input.trim().chars().map(|x| x == '.').collect());
}
let mut modifications = vec![false; n];
let mut modification_targets: Vec<usize> = vec![0; n];
for row in 0..n {
if !modifications[row] {
for rowi in 0..n {
if map[row] == map[rowi] && row != rowi {
modifications[rowi] = true;
modification_targets[rowi] = row;
}
}
}
}
let mut new_map: Vec<Vec<bool>> = Vec::new();
for row in 0..n {
if modifications[row] {
} else {
new_map.push(map[row].clone());
modification_targets[row] = new_map.len() - 1;
}
}
dbg!(&modifications, &modification_targets);
let n = new_map.len();
let map = new_map;
let mut rows: Vec<Row> = vec![
Row {
connections: Vec::new()
};
n
];
for row in 0..n {
let mut connections = vec![false; n];
for column in 0..m {
if map[row][column] {
for rowi in 0..n {
if row != rowi && map[rowi][column] {
connections[rowi] = true;
}
}
}
}
//dbg!(&connections);
for rowi in 0..n {
if connections[rowi] {
rows[row].connections.push(rowi);
}
}
}
//dbg!(&rows[198]);
let mut queries: Vec<((usize, usize), (usize, usize))> = Vec::new();
for _ in 0..q {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let (y1, x1, y2, x2): (usize, usize, usize, usize) = {
let mut iter = input.split_whitespace();
let mut y1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
let x1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
let mut y2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
let x2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
y1 = modification_targets[y1];
y2 = modification_targets[y2];
(y1, x1, y2, x2)
};
queries.push(((x1, y1), (x2, y2)));
}
let rows = rows;
let queries = queries;
for query in queries {
println!("{}", process_query(&rows, &map, query));
}
}
fn process_query(
map_rows: &Vec<Row>,
map: &Vec<Vec<bool>>,
query: ((usize, usize), (usize, usize)),
) -> i32 {
let mut steps = 1;
let rows = map_rows.len();
let mut used_rows = vec![false; rows];
if query.0 == query.1 {
return 0;
} else if query.0.0 == query.1.0 || query.0.1 == query.1.1 {
return 1;
}
let mut process_rows: Vec<usize> = Vec::new();
let mut advantages = vec![false; rows];
advantages[query.0.1] = true;
for row in 0..rows {
if map[row][query.0.0] {
process_rows.push(row);
used_rows[row] = true;
}
}
if used_rows[query.1.1] {
return 2;
}
loop {
dbg!(&process_rows);
if used_rows[query.1.1] {
return steps + 1;
}
let mut can_continue = false;
let mut new_process_rows: Vec<usize> = Vec::new();
let mut new_advantages = vec![false; rows];
let mut can_still_use = vec![false; rows];
let mut lowest_score = -1;
for row in process_rows {
for rowi in &map_rows[row].connections {
if (!used_rows[*rowi]) || can_still_use[*rowi] {
used_rows[*rowi] = true;
new_process_rows.push(*rowi);
can_continue = true;
if advantages[row] {
new_advantages[*rowi] = true;
}
if *rowi == 83 {
dbg!(advantages[row]);
}
if *rowi == query.1.1 {
if advantages[row] {
if lowest_score != -1 {
if map[row][query.1.0] {
lowest_score = i32::min(lowest_score, steps + 1);
} else {
lowest_score = i32::min(lowest_score, steps + 2);
can_still_use[*rowi] = true;
}
} else {
// Sometimes goes to wrong branch??????
if map[row][query.1.0] {
lowest_score = steps + 1;
} else {
lowest_score = steps + 2;
can_still_use[*rowi] = true;
}
}
} else {
dbg!(row, rowi);
if lowest_score != -1 {
if map[row][query.1.0] {
lowest_score = i32::min(lowest_score, steps + 2);
} else {
lowest_score = i32::min(lowest_score, steps + 3);
}
} else {
// Sometimes goes to wrong branch??????
if map[row][query.1.0] {
lowest_score = steps + 2;
} else {
lowest_score = steps + 3; // 9946 branch
}
}
can_still_use[*rowi] = true;
}
}
}
}
}
if lowest_score != -1 {
return lowest_score;
}
if !can_continue {
return -1;
}
process_rows = new_process_rows;
advantages = new_advantages;
steps += 2;
}
}
Test details
Test 1 (public)
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 4 6 5 .*.*** *...** *****. *..*.* ... |
| correct output |
|---|
| 1 0 3 3 -1 |
| user output |
|---|
| 1 0 3 3 -1 |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
]
[input/code.rs:48] &modification_targets = [
0,
1,
2,
3,
]
[input/code.rs:139] &process_rows = [
0,
]
[input/code.rs:139] &process_rows = [
3,
]
[input/code.rs:139] &process_rows = [
2,
]Test 2
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 10 10 .......... .....*.... ........*. *.*....*.. ... |
| correct output |
|---|
| 1 2 1 2 2 ... |
| user output |
|---|
| 1 2 1 2 2 ... |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
true,
false,
false,
false,
false,
false,
]
[input/code.rs:48] &modification_targets = [
0,
1,
2,
3,
2,
4,
5,
6,
7,
8,
]
[input/code.rs:139] &process_rows = [
0,
1,
3,
4,
6,
7,
8,
]
[input/code.rs:139] &process_rows = [
0,
1,
2,
6,
7,
8,
]
[input/code.rs:183] row = 0
[input/code.rs:183] rowi = 4
[input/code.rs:183] row = 2
[input/code.rs:183] rowi = 4
[input/code.rs:183] row = 6
[input/code.rs:183] rowi = 4
[input/code.rs:183] row = 7
[input/code.rs:183] rowi = 4
[input/code.rs:183] row = 8
[input/code.rs:183] rowi = 4Test 3
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 10 10 *...***.** *****.*... **..**.**. ..**.**.*. ... |
| correct output |
|---|
| 1 2 2 1 2 ... |
| user output |
|---|
| 1 2 2 1 2 ... |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
]
[input/code.rs:48] &modification_targets = [
0,
1,
2,
3,
4,
5,
6,
7,
8,
9,
]
[input/code.rs:139] &process_rows = [
0,
2,
4,
5,
6,
7,
]
[input/code.rs:183] row = 0
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 2
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 4
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 5
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 7
[input/code.rs:183] rowi = 8
[input/code.rs:139] &process_rows = [
0,
2,
4,
5,
6,
7,
]
[input/code.rs:183] row = 0
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 4
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 5
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 6
[input/code.rs:183] rowi = 8
[input/code.rs:183] row = 7
[input/code.rs:183] rowi = 8...Test 4
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 10 10 ***.*.**** ********** *.******** .*.***.**. ... |
| correct output |
|---|
| 3 4 2 3 4 ... |
| user output |
|---|
| 3 4 2 3 4 ... |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
true,
false,
false,
false,
false,
false,
]
[input/code.rs:48] &modification_targets = [
0,
1,
2,
3,
1,
4,
5,
6,
7,
8,
]
[input/code.rs:139] &process_rows = [
0,
6,
]
[input/code.rs:139] &process_rows = [
0,
4,
7,
]
[input/code.rs:183] row = 7
[input/code.rs:183] rowi = 8
[input/code.rs:139] &process_rows = [
7,
8,
]
[input/code.rs:139] &process_rows = [
0,
4,
7,
]
[input/code.rs:183] row = 7
[input/code.rs:183] rowi = 3
[input/code.rs:139] &process_rows = [
0,
6,
]
[input/code.rs:139] &process_rows = [
3,
6,
]
[input/code.rs:139] &process_rows = [
7,
8,
0,
]
[input/code.rs:139] &process_rows = [
4,
2,
]
[input/code.rs:139] &process_rows = [
0,
4,
7,
]
[input/code.rs:183] row = 7
[input/code.rs:183] rowi = 8Test 5
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 10 1 .****.**** **.**..*** ********** *******..* ... |
| correct output |
|---|
| 7 |
| user output |
|---|
| 7 |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
true,
false,
false,
true,
false,
false,
]
[input/code.rs:48] &modification_targets = [
0,
1,
2,
3,
2,
4,
5,
2,
6,
7,
]
[input/code.rs:139] &process_rows = [
1,
]
[input/code.rs:139] &process_rows = [
0,
6,
7,
]
[input/code.rs:139] &process_rows = [
4,
]Test 6
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 250 250 250 .*...*.....*******..**...*....... |
| correct output |
|---|
| 2 3 3 2 2 ... |
| user output |
|---|
| 2 3 3 2 2 ... |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
f...Test 7
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 250 250 250 ...*......**.**.*.*..**..*..**... |
| correct output |
|---|
| 2 2 2 2 3 ... |
| user output |
|---|
| 2 2 2 2 3 ... |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
f...Test 8
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 250 250 250 **..**..****.****.*.***.***..*... |
| correct output |
|---|
| 2 3 3 3 3 ... |
| user output |
|---|
| 2 3 3 3 3 ... |
Error:
[input/code.rs:48] &modifications = [
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
false,
f...Test 9
Group: 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 40 40 200000 ...*.**.*..*.............*.*..... |
| correct output |
|---|
| 2 2 2 2 2 ... |
| user output |
|---|
| (empty) |
Test 10
Group: 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 40 40 200000 **.**..*.*.*.******....****.*.... |
| correct output |
|---|
| 2 1 3 2 2 ... |
| user output |
|---|
| (empty) |
Test 11
Group: 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 40 40 200000 .*.*.**.*****.***.*.****.**.**... |
| correct output |
|---|
| 3 3 3 3 3 ... |
| user output |
|---|
| (empty) |
Test 12
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 80 80 200000 *....**.***..****...*.....*...... |
| correct output |
|---|
| 2 2 2 2 2 ... |
| user output |
|---|
| (empty) |
Test 13
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 80 80 200000 .***.*..*.***..*****....**...*... |
| correct output |
|---|
| 3 2 2 3 2 ... |
| user output |
|---|
| (empty) |
Test 14
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 80 80 200000 *******.*****.*..*..****...***... |
| correct output |
|---|
| 2 3 1 2 2 ... |
| user output |
|---|
| (empty) |
Test 15
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 250 250 200000 *....*..*..*..**..*.........**... |
| correct output |
|---|
| 3 2 2 2 2 ... |
| user output |
|---|
| (empty) |
Test 16
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 250 250 200000 ..*....*..*......*.**.*.*..***... |
| correct output |
|---|
| 2 2 2 2 2 ... |
| user output |
|---|
| (empty) |
Test 17
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 250 250 200000 *..*.*****.*********.****.****... |
| correct output |
|---|
| 3 3 2 2 2 ... |
| user output |
|---|
| (empty) |
Test 18
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 250 250 200000 *********.**********.******.**... |
| correct output |
|---|
| 3 3 3 3 3 ... |
| user output |
|---|
| (empty) |
Test 19
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 250 250 200000 .*****************************... |
| correct output |
|---|
| 104 422 145 93 65 ... |
| user output |
|---|
| (empty) |
Test 20
Group: 5
Verdict: RUNTIME ERROR
| input |
|---|
| 250 250 200000 ..****************************... |
| correct output |
|---|
| 57 155 38 65 98 ... |
| user output |
|---|
| 32 |
Error:
[input/code.rs:48] &modifications = [
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
true,
false,
tr...Test 21
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 250 250 200000 .*****************************... |
| correct output |
|---|
| 498 498 498 498 498 ... |
| user output |
|---|
| (empty) |
Test 22
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 1 10 * * . * ... |
| correct output |
|---|
| 0 1 1 0 0 ... |
| user output |
|---|
| 0 1 1 0 0 ... |
Error:
[input/code.rs:48] &modifications = [
false,
true,
false,
true,
true,
true,
true,
true,
true,
true,
]
[input/code.rs:48] &modification_targets = [
0,
0,
1,
0,
0,
2,
0,
0,
0,
2,
]Test 23
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1 10 10 ........*. 1 7 1 10 1 4 1 7 1 5 1 1 ... |
| correct output |
|---|
| 1 1 1 1 1 ... |
| user output |
|---|
| 1 1 1 1 1 ... |
Error:
[input/code.rs:48] &modifications = [
false,
]
[input/code.rs:48] &modification_targets = [
0,
]Test 24
Group: 5
Verdict: WRONG ANSWER
| input |
|---|
| 250 1 200000 * . * . ... |
| correct output |
|---|
| 1 1 1 1 1 ... |
| user output |
|---|
| 0 0 0 0 0 ... |
Feedback: Incorrect character on line 1 col 1: expected "1", got "0"
Error:
[input/code.rs:48] &modifications = [
false,
false,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,...Test 25
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 1 250 200000 *.*.*...*.*.**.***..**.*.*..**... |
| correct output |
|---|
| 1 1 1 1 1 ... |
| user output |
|---|
| 1 1 1 1 1 ... |
Error:
[input/code.rs:48] &modifications = [
false,
]
[input/code.rs:48] &modification_targets = [
0,
]Test 26
Group: 5
Verdict: WRONG ANSWER
| input |
|---|
| 250 250 200000 ................................. |
| correct output |
|---|
| 2 2 2 2 2 ... |
| user output |
|---|
| 1 1 1 1 1 ... |
Feedback: Incorrect character on line 1 col 1: expected "2", got "1"
Error:
[input/code.rs:48] &modifications = [
false,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,...Test 27
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 250 250 200000 ******************************... |
| correct output |
|---|
| 0 0 0 0 0 ... |
| user output |
|---|
| 0 0 0 0 0 ... |
Error:
[input/code.rs:48] &modifications = [
false,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,
true,...