CSES - Datatähti 2024 loppu - Results
Submission details
Task:Peli
Sender:ToukoP
Submission time:2024-01-20 16:22:45 +0200
Language:Rust
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1, 2details
#20.04 s1, 2details
#3--2details
#40.01 s1, 2details
#50.01 s1, 2details
#6--2details
#7--2details
#80.03 s1, 2details
#9--2details
#10--2details

Code

use std::{*, collections::VecDeque};

fn check(graph: &Vec<Vec<usize>>, n: usize, _m: usize, a: usize, b: usize, x: usize) -> bool {
    let mut dist = vec![usize::MAX; n + 1];
    let mut p = vec![0; n + 1];

    let mut visited = vec![false; n + 1];
    let mut odd = vec![false; n + 1];
    let mut even = vec![false; n + 1];

    let mut q = VecDeque::new();
    q.push_back(a);
    dist[a] = 0;
    visited[a] = true;

    while !q.is_empty() {
        if let Some(planet) = q.pop_front() {
            visited[planet] = true;
            for c in graph[planet].iter() {
                /*if *c == b && (dist[planet] % 2 == 0) == (x % 2 == 0) {
                    continue;
                }*/
                if dist[planet] + 1 % 2 == 0 {
                    even[*c] = true;
                } else {
                    odd[*c] = true;
                }
                if dist[planet] + 1 < dist[*c] {
                    dist[*c] = dist[planet] + 1;
                    p[*c] = planet;
                }
                if !visited[*c] {
                    q.push_back(*c);
                } 
            }
        } else {
            break;
        }
    }

    let mut d = 0;

    let mut visited2 = vec![false; n + 1];
    let mut planet = b;

    eprintln!("a: {a} b: {b} x: {x}");
    eprintln!("p: {:?}", p);
    eprintln!("d: {:?}", dist);

    while planet != a {
        eprintln!("> {}", planet);
        planet = p[planet];
        if visited2[planet] {
            return false;
        }
        visited2[planet] = true;
        d += 1;
    }

    if a == b {
        return x % 2 == 0;
    }
    eprintln!("d: {}", d);

    d <= x && if x % 2 == 0 { even[b] } else { odd[b] }
}

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);
    }

    println!("{:?}", 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:

input
2 1 100
1 2
1 1 0
1 2 0
2 1 0
...

correct output
YES
NO
NO
YES
NO
...

user output
[[], [2], [1]]
YES
NO
NO
YES
...
Truncated

Error:
a: 1 b: 1 x: 0
p: [0, 0, 1]
d: [18446744073709551615, 0, 1]
a: 1 b: 2 x: 0
p: [0, 0, 1]
d:...

Test 2

Group: 1, 2

Verdict:

input
50 49 100
33 34
7 8
49 50
47 48
...

correct output
NO
NO
NO
NO
NO
...

user output
[[], [2], [3, 1], [4, 2], [3, ...
Truncated

Error:
a: 14 b: 29 x: 16
p: [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 14, 15, 16, 17, 18...

Test 3

Group: 2

Verdict:

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:

input
12 12 100
9 10
2 3
1 12
1 2
...

correct output
NO
NO
NO
NO
NO
...

user output
[[], [12, 2], [3, 1], [2, 4], ...
Truncated

Error:
a: 4 b: 7 x: 16
p: [0, 2, 3, 4, 0, 4, 5, 6, 7, 8, 11, 12, 1]
d: [18446744073709551615, 3,...

Test 5

Group: 1, 2

Verdict:

input
11 11 100
10 11
7 8
1 2
5 6
...

correct output
YES
YES
YES
YES
YES
...

user output
[[], [2, 11], [1, 3], [4, 2], ...
Truncated

Error:
a: 3 b: 7 x: 16
p: [0, 2, 3, 0, 3, 4, 5, 6, 7, 10, 11, 1]
d: [18446744073709551615, 2, 1,...

Test 6

Group: 2

Verdict:

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:

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:

input
50 99 100
40 47
34 50
44 47
15 16
...

correct output
YES
YES
YES
YES
YES
...

user output
[[], [35, 9, 5, 4, 2], [6, 3, ...
Truncated

Error:
a: 37 b: 24 x: 46
p: [0, 2, 3, 37, 1, 17, 2, 25, 9, 44, 3, 3, 6, 34, 50, 5, 43, 37, 13, 6,...

Test 9

Group: 2

Verdict:

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:

input
2500 4999 100000
2023 2218
23 51
1020 1272
11 114
...

correct output
YES
YES
YES
YES
YES
...

user output
(empty)