Submission #66772066
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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 |
|
|
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 |