結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー fukafukatani
提出日時 2020-09-26 10:03:39
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 6,026 bytes
コンパイル時間 15,387 ms
コンパイル使用メモリ 384,772 KB
実行使用メモリ 441,344 KB
最終ジャッジ日時 2024-12-22 14:02:33
合計ジャッジ時間 27,643 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24 TLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `i`
  --> src/main.rs:22:9
   |
22 |     for i in 0..n {
   |         ^ help: if this is intentional, prefix it with an underscore: `_i`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: function `read_vec` is never used
  --> src/main.rs:65:4
   |
65 | fn read_vec<T: std::str::FromStr>() -> Vec<T> {
   |    ^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;
use std::ops::Bound::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();

    let mut words = vec![];
    for i in 0..n {
        let word = read::<String>().chars().collect::<Vec<_>>();
        words.push(word);
    }

    let mut cons = vec![];
    for i in 0..n {
        let w1 = &words[i];
        for j in i + 1..n {
            let w2 = &words[j];
            if w1[0] == w2[0] || w1[1..3] == w2[1..3] {
                cons.push((i as i32 + 1, j as i32 + 1));
            }
            if w1[0] == w2[2] || w1[1..3] == w2[0..2] {
                cons.push((i as i32 + 1, -(j as i32 + 1)));
            }
            if w1[2] == w2[0] || w1[0..2] == w2[1..3] {
                cons.push((-(i as i32 + 1), j as i32 + 1));
            }
            if w1[2] == w2[2] || w1[0..2] == w2[0..2] {
                cons.push((-(i as i32 + 1), -(j as i32 + 1)));
            }
        }
    }
    if let Some(result) = two_sat(n, &cons) {
        for i in 0..n {
            if result[i] {
                println!("{}{} {}", words[i][0], words[i][1], words[i][2]);
            } else {
                println!("{} {}{}", words[i][0], words[i][1], words[i][2]);
            }
        }
    } else {
        println!("Impossible");
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

struct SCC {
    n: usize,
    ncc: usize,
    g: Vec<Vec<usize>>,  // graph in adjacent list
    rg: Vec<Vec<usize>>, // reverse graph
    cmp: Vec<usize>,     // topological order
}

impl SCC {
    fn new(n: usize) -> Self {
        SCC {
            n: n,
            ncc: n + 1,
            g: vec![Vec::new(); n],
            rg: vec![Vec::new(); n],
            cmp: vec![0; n],
        }
    }
    fn add_edge(&mut self, from: usize, to: usize) {
        self.g[from].push(to);
        self.rg[to].push(from);
    }
    fn dfs(&self, v: usize, used: &mut [bool], vs: &mut Vec<usize>) {
        used[v] = true;
        for &w in self.g[v].iter() {
            if !used[w] {
                self.dfs(w, used, vs);
            }
        }
        vs.push(v);
    }
    fn rdfs(&self, v: usize, k: usize, used: &mut [bool], cmp: &mut [usize]) {
        used[v] = true;
        cmp[v] = k;
        for &w in self.rg[v].iter() {
            if !used[w] {
                self.rdfs(w, k, used, cmp);
            }
        }
    }
    fn scc(&mut self) -> usize {
        let n = self.n;
        let mut used = vec![false; n];
        let mut vs = Vec::new();
        let mut cmp = vec![0; n];
        for v in 0..n {
            if !used[v] {
                self.dfs(v, &mut used, &mut vs);
            }
        }
        for u in used.iter_mut() {
            *u = false;
        }
        let mut k = 0;
        for &t in vs.iter().rev() {
            if !used[t] {
                self.rdfs(t, k, &mut used, &mut cmp);
                k += 1;
            }
        }
        self.ncc = k;
        self.cmp = cmp;
        k
    }
    #[allow(dead_code)]
    fn top_order(&self) -> Vec<usize> {
        assert!(self.ncc <= self.n);
        self.cmp.clone()
    }
    /*
     * Returns a dag whose vertices are scc's, and whose edges are those of the original graph.
     */
    #[allow(dead_code)]
    fn dag(&self) -> Vec<Vec<usize>> {
        assert!(self.ncc <= self.n);
        let ncc = self.ncc;
        let mut ret = vec![HashSet::new(); ncc];
        let n = self.n;
        for i in 0..n {
            for &to in self.g[i].iter() {
                if self.cmp[i] != self.cmp[to] {
                    assert!(self.cmp[i] < self.cmp[to]);
                    ret[self.cmp[i]].insert(self.cmp[to]);
                }
            }
        }
        ret.into_iter()
            .map(|set| set.into_iter().collect())
            .collect()
    }
    #[allow(dead_code)]
    fn rdag(&self) -> Vec<Vec<usize>> {
        assert!(self.ncc <= self.n);
        let ncc = self.ncc;
        let mut ret = vec![HashSet::new(); ncc];
        let n = self.n;
        for i in 0..n {
            for &to in self.g[i].iter() {
                if self.cmp[i] != self.cmp[to] {
                    assert!(self.cmp[i] < self.cmp[to]);
                    ret[self.cmp[to]].insert(self.cmp[i]);
                }
            }
        }
        ret.into_iter()
            .map(|set| set.into_iter().collect())
            .collect()
    }
}

/**
 * 2-SAT solver.
 * n: the number of variables (v_1, ..., v_n)
 * cons: constraints, given in 2-cnf
 * i (1 <= i <= n) means v_i, -i (1 <= i <= n) means not v_i.
 * Returns: None if there's no assignment that satisfies cons.
 * Otherwise, it returns an assignment that safisfies cons. (true: true, false: false)
 * Dependencies: SCC.rs
 * Verified by: Codeforces #400 D
 *              (http://codeforces.com/contest/776/submission/24957215)
 */
fn two_sat(n: usize, cons: &[(i32, i32)]) -> Option<Vec<bool>> {
    let mut scc = SCC::new(2 * n);
    let ni = n as i32;
    for &(c1, c2) in cons.iter() {
        let x = if c1 > 0 { c1 - 1 + ni } else { -c1 - 1 } as usize;
        let y = if c2 > 0 { c2 - 1 } else { -c2 - 1 + ni } as usize;
        scc.add_edge(x, y);
        scc.add_edge((y + n) % (2 * n), (x + n) % (2 * n));
    }
    scc.scc();
    let mut result = vec![false; n];
    let top_ord = scc.top_order();
    for i in 0..n {
        if top_ord[i] == top_ord[i + n] {
            return None;
        }
        result[i] = top_ord[i] > top_ord[i + n];
    }
    Some(result)
}
0