Submission #1450443
Source Code Expand
use std::io; use std::io::{Read, BufReader}; use std::cmp; fn next_token<R: Read>(reader: &mut R) -> Vec<u8> { let mut buf: [u8; 1] = [0]; let mut read_chars = false; let mut ret: Vec<u8> = vec![]; loop { if reader.read(&mut buf).unwrap() == 0 { break; } else { if buf[0] == '\r' as u8 || buf[0] == '\n' as u8 || buf[0] == ' ' as u8 { if read_chars { break; } } else { read_chars = true; ret.push(buf[0]); } } }; ret } fn next_i64<R: Read>(reader: &mut R) -> i64 { let token = next_token(reader); let mut ret: i64 = 0; let mut sgn = false; for c in token { if '0' as u8 <= c && c <= '9' as u8 { ret = ret * 10 + (c - ('0' as u8)) as i64; } else if '-' as u8 == c { sgn = true; } }; ret * if sgn { -1 } else { 1 } } fn next_i32<R: Read>(reader: &mut R) -> i32 { next_i64(reader) as i32 } fn assign_sign(v: usize, rt: usize, tree: &Vec<Vec<usize>>, ans: &mut Vec<i32>) { let mut x = 1; for &w in &tree[v] { if w == rt { continue; } assign_sign(w, v, tree, ans); x ^= 1; } ans[v] = x; } fn make_aux_graph(v: usize, rt: usize, tree: &Vec<Vec<usize>>, aux: &mut Vec<Vec<usize>>) -> usize { let mut last_ch: Option<usize> = None; for &w in &tree[v] { if w == rt { continue; } let free = make_aux_graph(w, v, tree, aux); match last_ch { Some(l) => { aux[l].push(free); aux[free].push(l); last_ch = None; }, None => { last_ch = Some(free); } } } match last_ch { Some(l) => l, None => v } } fn decide_ans(v: usize, sto: i32, aux: &Vec<Vec<usize>>, ans: &mut Vec<i32>) { if ans[v] != -2 { return; } ans[v] = sto; for &w in &aux[v] { decide_ans(w, -sto, aux, ans); } } fn main() { let buf = &mut BufReader::new(io::stdin()); let n = next_i32(buf) as usize; let mut a = vec![vec![]; n]; let mut b = vec![vec![]; n]; let mut ra = 0; let mut rb = 0; for i in 0..n { let par = next_i32(buf); if par != -1 { let par = (par - 1) as usize; a[i].push(par); a[par].push(i); } else { ra = i; } } for i in 0..n { let par = next_i32(buf); if par != -1 { let par = (par - 1) as usize; b[i].push(par); b[par].push(i); } else { rb = i; } } let mut sgn_a = vec![0; n]; let mut sgn_b = vec![0; n]; assign_sign(ra, n, &a, &mut sgn_a); assign_sign(rb, n, &b, &mut sgn_b); if sgn_a != sgn_b { println!("IMPOSSIBLE"); return; } println!("POSSIBLE"); let mut aux = vec![vec![]; n]; make_aux_graph(ra, n, &a, &mut aux); make_aux_graph(rb, n, &b, &mut aux); let mut ans = vec![-2; n]; for i in 0..n { if sgn_a[i] == 0 { ans[i] = 0; } else { decide_ans(i, 1, &aux, &mut ans); } } for i in 0..n { if i == n - 1 { println!("{}", ans[i]); } else { print!("{} ", ans[i]); } } }
Submission Info
Submission Time | |
---|---|
Task | F - Two Trees |
User | semiexp |
Language | Rust (1.15.1) |
Score | 1700 |
Code Size | 3627 Byte |
Status | AC |
Exec Time | 94 ms |
Memory | 32636 KB |
Compile Error
warning: unused import: `std::cmp`, #[warn(unused_imports)] on by default --> ./Main.rs:3:5 | 3 | use std::cmp; | ^^^^^^^^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1700 / 1700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt, subtask_1_56.txt, subtask_1_57.txt, subtask_1_58.txt, subtask_1_59.txt, subtask_1_60.txt, subtask_1_61.txt, subtask_1_62.txt, subtask_1_63.txt, subtask_1_64.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 2 ms | 4352 KB |
sample_02.txt | AC | 2 ms | 4352 KB |
sample_03.txt | AC | 2 ms | 4352 KB |
subtask_1_01.txt | AC | 2 ms | 4352 KB |
subtask_1_02.txt | AC | 2 ms | 4352 KB |
subtask_1_03.txt | AC | 27 ms | 10492 KB |
subtask_1_04.txt | AC | 56 ms | 18428 KB |
subtask_1_05.txt | AC | 44 ms | 18684 KB |
subtask_1_06.txt | AC | 19 ms | 8828 KB |
subtask_1_07.txt | AC | 51 ms | 16764 KB |
subtask_1_08.txt | AC | 19 ms | 10492 KB |
subtask_1_09.txt | AC | 26 ms | 12540 KB |
subtask_1_10.txt | AC | 49 ms | 15740 KB |
subtask_1_11.txt | AC | 10 ms | 6396 KB |
subtask_1_12.txt | AC | 66 ms | 20476 KB |
subtask_1_13.txt | AC | 31 ms | 12540 KB |
subtask_1_14.txt | AC | 10 ms | 6780 KB |
subtask_1_15.txt | AC | 22 ms | 8444 KB |
subtask_1_16.txt | AC | 28 ms | 14588 KB |
subtask_1_17.txt | AC | 20 ms | 10492 KB |
subtask_1_18.txt | AC | 70 ms | 28796 KB |
subtask_1_19.txt | AC | 50 ms | 18684 KB |
subtask_1_20.txt | AC | 92 ms | 29692 KB |
subtask_1_21.txt | AC | 49 ms | 22652 KB |
subtask_1_22.txt | AC | 50 ms | 22524 KB |
subtask_1_23.txt | AC | 82 ms | 29180 KB |
subtask_1_24.txt | AC | 94 ms | 25084 KB |
subtask_1_25.txt | AC | 35 ms | 20732 KB |
subtask_1_26.txt | AC | 41 ms | 20732 KB |
subtask_1_27.txt | AC | 79 ms | 28412 KB |
subtask_1_28.txt | AC | 53 ms | 18684 KB |
subtask_1_29.txt | AC | 83 ms | 28924 KB |
subtask_1_30.txt | AC | 47 ms | 20860 KB |
subtask_1_31.txt | AC | 54 ms | 24060 KB |
subtask_1_32.txt | AC | 81 ms | 28412 KB |
subtask_1_33.txt | AC | 77 ms | 25084 KB |
subtask_1_34.txt | AC | 35 ms | 20732 KB |
subtask_1_35.txt | AC | 42 ms | 20732 KB |
subtask_1_36.txt | AC | 79 ms | 29820 KB |
subtask_1_37.txt | AC | 81 ms | 29564 KB |
subtask_1_38.txt | AC | 86 ms | 29436 KB |
subtask_1_39.txt | AC | 83 ms | 30588 KB |
subtask_1_40.txt | AC | 81 ms | 29180 KB |
subtask_1_41.txt | AC | 84 ms | 30076 KB |
subtask_1_42.txt | AC | 63 ms | 29308 KB |
subtask_1_43.txt | AC | 81 ms | 29692 KB |
subtask_1_44.txt | AC | 79 ms | 29948 KB |
subtask_1_45.txt | AC | 82 ms | 30332 KB |
subtask_1_46.txt | AC | 84 ms | 30588 KB |
subtask_1_47.txt | AC | 88 ms | 29308 KB |
subtask_1_48.txt | AC | 88 ms | 29948 KB |
subtask_1_49.txt | AC | 63 ms | 29692 KB |
subtask_1_50.txt | AC | 82 ms | 29308 KB |
subtask_1_51.txt | AC | 83 ms | 28796 KB |
subtask_1_52.txt | AC | 83 ms | 30076 KB |
subtask_1_53.txt | AC | 87 ms | 29052 KB |
subtask_1_54.txt | AC | 87 ms | 28668 KB |
subtask_1_55.txt | AC | 87 ms | 29436 KB |
subtask_1_56.txt | AC | 64 ms | 29820 KB |
subtask_1_57.txt | AC | 92 ms | 29564 KB |
subtask_1_58.txt | AC | 87 ms | 29308 KB |
subtask_1_59.txt | AC | 80 ms | 30588 KB |
subtask_1_60.txt | AC | 82 ms | 29308 KB |
subtask_1_61.txt | AC | 80 ms | 29436 KB |
subtask_1_62.txt | AC | 87 ms | 29308 KB |
subtask_1_63.txt | AC | 66 ms | 32636 KB |
subtask_1_64.txt | AC | 82 ms | 29308 KB |