結果

問題 No.1266 7 Colors
ユーザー StrorkisStrorkis
提出日時 2020-10-24 00:41:57
言語 Rust
(1.72.1)
結果
AC  
実行時間 199 ms / 3,000 ms
コード長 4,235 bytes
コンパイル時間 2,410 ms
コンパイル使用メモリ 149,880 KB
実行使用メモリ 22,176 KB
最終ジャッジ日時 2023-09-28 19:46:59
合計ジャッジ時間 6,998 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 87 ms
6,712 KB
testcase_04 AC 180 ms
15,864 KB
testcase_05 AC 99 ms
7,196 KB
testcase_06 AC 180 ms
17,200 KB
testcase_07 AC 199 ms
19,488 KB
testcase_08 AC 178 ms
16,132 KB
testcase_09 AC 149 ms
12,904 KB
testcase_10 AC 148 ms
11,992 KB
testcase_11 AC 101 ms
8,500 KB
testcase_12 AC 116 ms
9,600 KB
testcase_13 AC 129 ms
10,680 KB
testcase_14 AC 93 ms
7,212 KB
testcase_15 AC 196 ms
19,772 KB
testcase_16 AC 123 ms
9,876 KB
testcase_17 AC 188 ms
18,984 KB
testcase_18 AC 92 ms
22,176 KB
testcase_19 AC 90 ms
21,356 KB
testcase_20 AC 90 ms
21,280 KB
testcase_21 AC 30 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

use std::io::{self, BufRead, Write};
use std::str::FromStr;

struct Dsu {
    n: usize,
    parent_or_size: Vec<usize>,
}

impl Dsu {
    fn new(n: usize) -> Dsu {
        Dsu { n, parent_or_size: vec![!1; n] }
    }

    fn merge(&mut self, a: usize, b: usize) -> usize {
        let (mut x, mut y) = (self.leader(a), self.leader(b));
        if x == y { return x; }
        if !self.parent_or_size[x] < !self.parent_or_size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent_or_size[x] -= !self.parent_or_size[y];
        self.parent_or_size[y] = x;
        x
    }

    fn leader(&mut self, a: usize) -> usize {
        if self.parent_or_size[a] >= self.n { return a; }
        self.parent_or_size[a] = self.leader(self.parent_or_size[a]);
        self.parent_or_size[a]
    }

    fn size(&mut self, a: usize) -> usize {
        let x = self.leader(a);
        !self.parent_or_size[x]
    }
}

struct Solver<'a> {
    reader: io::BufReader<io::StdinLock<'a>>,
    writer: io::BufWriter<io::StdoutLock<'a>>,
}

impl Solver<'_> {
    fn read_line(&mut self) -> String {
        let mut input = String::new();
        self.reader.read_line(&mut input).unwrap();
        input
    }

    fn read_triple<T1, T2, T3>(&mut self) -> (T1, T2, T3)
        where T1: FromStr, T2: FromStr, T3: FromStr
    {
        let input = self.read_line();
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        )
    }

    fn read_char_vec(&mut self) -> Vec<char> {
        let input = self.read_line();
        input.trim_end().chars().collect()
    }

    fn read_char_mat(&mut self, n: usize) -> Vec<Vec<char>> {
        let mut res = Vec::with_capacity(n);
        for _ in 0..n {
            let tmp = self.read_char_vec();
            res.push(tmp);
        }
        res
    }

    fn read_pair<T1: FromStr, T2: FromStr>(&mut self) -> (T1, T2) {
        let input = self.read_line();
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        )
    }    

    fn writeln<T: std::fmt::Display>(&mut self, ans: T) {
        writeln!(self.writer, "{}", ans).unwrap();
    }

    fn solve(&mut self) {
        let (n, m, q) = self.read_triple::<usize, usize, usize>();
        let mut s = self.read_char_mat(n);

        let mut g = vec![vec![]; n];
        for _ in 0..m {
            let (u, v) = self.read_pair::<usize, usize>();
            let (u, v) = (u - 1, v - 1);
            g[u].push(v);
            g[v].push(u);
        }

        let mut dsu = Dsu::new(n * 7);
        for i in 0..n {
            for j in 0..7 {
                if s[i][j] != '1' { continue; }
                if s[i][(j + 1) % 7] == '1' {
                    dsu.merge(i * 7 + j, i * 7 + (j + 1) % 7);
                }
                for &k in &g[i] {
                    if s[k][j] != '1' { continue; }
                    dsu.merge(i * 7 + j, k * 7 + j);
                }
            }
        }

        for _ in 0..q {
            let (t, x, y) = self.read_triple::<u8, usize, usize>();
            if t == 1 {
                let (x, y) = (x - 1, y - 1);
                s[x][y] = '1';
                if s[x][(y + 6) % 7] == '1' {
                    dsu.merge(x * 7 + y, x * 7 + (y + 6) % 7);
                }
                if s[x][(y + 1) % 7] == '1' {
                    dsu.merge(x * 7 + y, x * 7 + (y + 1) % 7);
                }
                for &z in &g[x] {
                    if s[z][y] != '1' { continue; }
                    dsu.merge(x * 7 + y, z * 7 + y);
                }
            } else {
                let x = x - 1;
                self.writeln(dsu.size(x * 7));
            }
        }
    }

    fn run() {
        let (stdin, stdout) = (io::stdin(), io::stdout());
        let reader = io::BufReader::new(stdin.lock());
        let writer = io::BufWriter::new(stdout.lock());
        let mut solver = Solver { reader, writer };
        solver.solve();
    }
}

fn main() {
    Solver::run();
}
0