結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー 👑 ArcAki
提出日時 2024-08-13 03:12:40
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 4,172 bytes
コンパイル時間 14,720 ms
コンパイル使用メモリ 377,696 KB
実行使用メモリ 40,192 KB
最終ジャッジ日時 2024-08-13 03:13:24
合計ジャッジ時間 41,257 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{self, BufRead};
use std::mem::swap;

struct UnionFind{
    parent: Vec<usize>,
    num: Vec<i64>,
}

impl UnionFind{
    fn new(n: usize)->Self{
        let parent = (0..n).into_iter().collect();
        let num = vec![1; n];
        UnionFind{
            parent, num,
        }
    }
    fn find(&mut self, x: usize)->usize{
        if x==self.parent[x]{return x;}
        self.parent[x] = self.find(self.parent[x]);
        self.parent[x]
    }

    fn union(&mut self, u: usize, v: usize){
        let (mut pu, mut pv) = (self.find(u), self.find(v));
        if pu==pv{return;}
        if self.num[pu] < self.num[pv]{
            swap(&mut pu, &mut pv);
        }
        self.num[pu] += self.num[pv];
        self.parent[pv] = pu;
    }

    fn same(&mut self, u: usize, v: usize)->bool{
        self.find(u)==self.find(v)
    }
}

struct CycleFinder {
    n: usize,
    edge: Vec<Vec<usize>>,
    went: Vec<bool>,
    used: Vec<bool>,
    cycle: Vec<bool>,
    way: Vec<usize>,
}

impl CycleFinder{
    fn new(n: usize)->Self{
        let edge = vec![Vec::new(); n];
        let went = vec![false; n];
        let used = vec![false; n];
        let cycle = vec![false; n];
        let way = Vec::new();
        CycleFinder{n, edge, went, used, cycle, way}
    }

    fn add_edge(&mut self, u: usize, v: usize){
        assert!(u < self.n && v < self.n);
        self.edge[u].push(v);
        self.edge[v].push(u);
    }

    fn build(&mut self){
        for i in 0..self.n{
            if self.used[i]{continue}
            self._dfs(i, !0);
        }
    }

    fn _dfs(&mut self, x: usize, pre: usize) {
        self.went[x] = true;
        self.way.push(x);
        let edges_ptr = self.edge[x].as_ptr();
        let edges_len = self.edge[x].len();
        for i in 0..edges_len {
            let nex = unsafe { *edges_ptr.add(i) };
            if self.used[nex] || nex==pre{
                continue;
            }
            if self.went[nex] {
                let t = nex;
                let mut p = self.way.len() - 1;
                while self.way[p] != t {
                    self.cycle[self.way[p]] = true;
                    p -= 1;
                }
                self.cycle[t] = true;
            } else {
                self._dfs(nex, x);
            }
        }
        self.used[x] = true;
        self.way.pop();
    }


    fn include_cycle(&self)->Vec<bool>{
        self.cycle.clone()
    }
}

fn main() {
    //input! {
    //    n: usize, m: usize, q: usize,
    //    e: [(usize, usize); m],
    //    query: [(usize, usize); q]
    //}
    //ここからの入力はgptです…やりたいことはただ以上のようなものです。
    let stdin = io::stdin();
    let mut iterator = stdin.lock().lines();
    let first_line = iterator.next().unwrap().unwrap();
    let mut iter = first_line.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();
    let q: usize = iter.next().unwrap().parse().unwrap();
    let mut e = Vec::with_capacity(m);
    for _ in 0..m {
        let line = iterator.next().unwrap().unwrap();
        let mut iter = line.split_whitespace();
        let u: usize = iter.next().unwrap().parse().unwrap();
        let v: usize = iter.next().unwrap().parse().unwrap();
        e.push((u, v));
    }
    let mut query = Vec::with_capacity(q);
    for _ in 0..q {
        let line = iterator.next().unwrap().unwrap();
        let mut iter = line.split_whitespace();
        let u: usize = iter.next().unwrap().parse().unwrap();
        let v: usize = iter.next().unwrap().parse().unwrap();
        query.push((u, v));
    }
    //↑ここまでの入力はgptです。
    let mut cf = CycleFinder::new(n);
    for &(u, v) in &e{
        cf.add_edge(u-1, v-1);
    }
    cf.build();
    let cycle = cf.include_cycle();
    let mut uf = UnionFind::new(n);
    for &(u, v) in &e{
        if !(cycle[u-1]&&cycle[v-1]){
            uf.union(u-1, v-1);
        }
    }
    for &(u, v) in &query{
        if uf.same(u-1, v-1){
            println!("Yes");
        } else {
            println!("No");
        }
    }
}
0