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
AC × 3
AC × 70
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