結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
ユーザー ArcAkiArcAki
提出日時 2024-08-13 03:24:52
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 4,481 bytes
コンパイル時間 12,918 ms
コンパイル使用メモリ 377,320 KB
実行使用メモリ 17,920 KB
最終ジャッジ日時 2024-08-13 03:25:15
合計ジャッジ時間 21,875 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 10 ms
5,376 KB
testcase_09 AC 13 ms
5,376 KB
testcase_10 AC 323 ms
5,376 KB
testcase_11 AC 167 ms
5,376 KB
testcase_12 AC 9 ms
5,376 KB
testcase_13 AC 1,160 ms
17,920 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashSet;
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>,
    cycle_edge: HashSet<(usize, 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();
        let cycle_edge = HashSet::new();
        CycleFinder{n, edge, went, used, cycle, way, cycle_edge}
    }

    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;
                self.cycle_edge.insert((self.way[p], t));
                while self.way[p] != t {
                    self.cycle[self.way[p]] = true;
                    p -= 1;
                    self.cycle_edge.insert((self.way[p], self.way[p+1]));
                }
                self.cycle[t] = true;
            } else {
                self._dfs(nex, x);
            }
        }
        self.used[x] = true;
        self.way.pop();
    }


    fn include_cycle(&self)->HashSet<(usize, usize)>{
        self.cycle_edge.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.contains(&(u-1, v-1))&&!cycle.contains(&(v-1, u-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