Submission #66772066


Source Code Expand

Copy
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
#![allow(clippy::collapsible_else_if)]
#![allow(clippy::ptr_arg)]
#![allow(unexpected_cfgs)]
use itertools::Itertools;
use proconio::{
fastout, input, input_interactive,
marker::{Chars, Usize1},
};
use rand::rngs::ThreadRng;
use rand::Rng;
use rand::RngCore;
use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha8Rng;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
#![allow(clippy::collapsible_else_if)]
#![allow(clippy::ptr_arg)]
#![allow(unexpected_cfgs)]
use itertools::Itertools;
use proconio::{
    fastout, input, input_interactive,
    marker::{Chars, Usize1},
};
use rand::rngs::ThreadRng;
use rand::Rng;
use rand::RngCore;
use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha8Rng;
use std::collections::BinaryHeap;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::mem::swap;
use std::time::Instant;
use std::{cmp::Reverse, vec};
use superslice::Ext; //lower_bound,upper_bound

use std::fs::{File, OpenOptions};
use std::io::{BufWriter, Write};

use std::cell::RefCell;
use std::cmp::Ordering;
use std::rc::{Rc, Weak};

//const MOD: usize = 1e9 as usize + 7;
const MOD: usize = 998244353;
// const MOD: usize = 2147483647;

#[macro_export]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $( $y: expr ),+) => {
        std::cmp::max($x, max!($( $y ),+))
    }
}
#[macro_export]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $( $y: expr ),+) => {
        std::cmp::min($x, min!($( $y ),+))
    }
}
pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.0
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}
#[derive(PartialEq)]
enum SubMode {
    Solve,
    NaiveSolve,
    Compare,
}
#[derive(Debug)]
struct Input {
    n: usize,
    m: usize,
    edges: Vec<(usize, usize, usize)>,
}
fn get_input() -> Input {
    input! {
        n:usize,
        m:usize,
        edges:[(Usize1,Usize1,usize);m],
    }
    Input { n, m, edges }
}
#[derive(PartialEq, Debug)]
struct Output {
    out: i64,
}
fn print_output(output: &Output) {
    println!("{}", output.out);
}
fn solve(input: &Input) -> Output {
    let mut graph = vec![vec![]; input.n];
    for &(u, v, w) in &input.edges {
        graph[u].push((v, w));
    }
    let mut dist = vec![usize::MAX; input.n];
    dist[0] = 0;
    let mut cycles = vec![];
    dfs(0, 0, &graph, &mut dist, &mut cycles);
    if dist[input.n - 1] == usize::MAX {
        return Output { out: -1 };
    }
    let mut base = vec![];
    for mut c in cycles {
        for &b in &base {
            c = min!(c, c ^ b);
        }
        if c > 0 {
            base.push(c);
        }
    }
    let mut out = dist[input.n - 1];
    for &b in &base {
        out = min!(out, out ^ b);
    }
    Output { out: out as i64 }
}
fn dfs(
    u: usize,
    cur_xor: usize,
    graph: &Vec<Vec<(usize, usize)>>,
    dist: &mut Vec<usize>,
    cycles: &mut Vec<usize>,
) {
    dist[u] = cur_xor;
    for &(v, w) in &graph[u] {
        if dist[v] != usize::MAX {
            cycles.push(cur_xor ^ w ^ dist[v]);
        } else {
            dfs(v, cur_xor ^ w, graph, dist, cycles);
        }
    }
}
fn main() {
    #[allow(unused_variables)]
    let t = 1; //t個の問題に答える、みたいなのだったらここを変える
    #[cfg(not(feature = "compare"))]
    let sub_mode = SubMode::Solve;
    #[cfg(feature = "compare")]
    let sub_mode = SubMode::Compare;
    for _ in 0..t {
        match sub_mode {
            SubMode::Solve => {
                let input = get_input();
                let output = solve(&input);
                print_output(&output);
            }
            #[cfg(feature = "compare")]
            SubMode::Compare => {
                let start_time = Instant::now();
                let time_limit = 3000;
                let mut loop_count = 0;
                loop {
                    loop_count += 1;
                    if loop_count % 100 == 0 {
                        let elapsed_time = start_time.elapsed().as_millis();
                        if elapsed_time > time_limit as u128 {
                            println!("Checked with {} cases. No diviation", loop_count);
                            break;
                        }
                    }
                    let input = generate_random_input();
                    let output = solve(&input);
                    let naive_output = naive_solve(&input);
                    if output == naive_output {
                        //do nothing
                    } else {
                        println!("NG");
                        println!("input");
                        println!("{:?}", input);
                        println!("output");
                        println!("{:?}", output);
                        println!("naive_output");
                        println!("{:?}", naive_output);
                        break;
                    }
                }
            }
            _ => {}
        }
    }
}
///////////////////////////////////////////////////
/// 比較用                  /////////
/// ///////////////////////////////////////////////
#[cfg(feature = "compare")]
fn naive_solve(input: &Input) -> Output {
    solve(input)
}
#[cfg(feature = "compare")]
fn generate_random_input() -> Input {
    let mut rng = rand::thread_rng();
    Input {}
}

Submission Info

Submission Time
Task D - XOR Shortest Walk
User Daichi124
Language Rust (rustc 1.70.0)
Score 0
Code Size 5680 Byte
Status WA
Exec Time 2 ms
Memory 2288 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 30
WA × 3
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 1940 KiB
hand_02.txt AC 1 ms 1868 KiB
hand_03.txt AC 1 ms 1740 KiB
hand_04.txt AC 1 ms 1976 KiB
hand_05.txt AC 1 ms 1908 KiB
hand_06.txt WA 1 ms 1872 KiB
hand_07.txt WA 1 ms 1928 KiB
hand_08.txt WA 1 ms 2072 KiB
random_01.txt AC 1 ms 1952 KiB
random_02.txt AC 1 ms 2212 KiB
random_03.txt AC 1 ms 1880 KiB
random_04.txt AC 1 ms 2000 KiB
random_05.txt AC 1 ms 1944 KiB
random_06.txt AC 1 ms 2012 KiB
random_07.txt AC 1 ms 1972 KiB
random_08.txt AC 1 ms 2080 KiB
random_09.txt AC 1 ms 1936 KiB
random_10.txt AC 2 ms 2248 KiB
random_11.txt AC 1 ms 1884 KiB
random_12.txt AC 1 ms 2064 KiB
random_13.txt AC 1 ms 1932 KiB
random_14.txt AC 1 ms 1792 KiB
random_15.txt AC 1 ms 2092 KiB
random_16.txt AC 1 ms 1964 KiB
random_17.txt AC 1 ms 2288 KiB
random_18.txt AC 1 ms 2084 KiB
random_19.txt AC 1 ms 2084 KiB
random_20.txt AC 1 ms 2044 KiB
random_21.txt AC 1 ms 2188 KiB
random_22.txt AC 1 ms 1968 KiB
sample_01.txt AC 1 ms 2004 KiB
sample_02.txt AC 1 ms 1932 KiB
sample_03.txt AC 1 ms 1964 KiB


2025-06-16 (Mon)
02:27:06 +09:00