結果
| 問題 |
No.2160 みたりのDominator
|
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2022-12-11 23:08:36 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 144 ms / 2,000 ms |
| コード長 | 17,809 bytes |
| コンパイル時間 | 23,933 ms |
| コンパイル使用メモリ | 383,972 KB |
| 実行使用メモリ | 50,572 KB |
| 最終ジャッジ日時 | 2024-10-15 18:05:11 |
| 合計ジャッジ時間 | 31,739 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 93 |
コンパイルメッセージ
warning: unused import: `std::io::Write` --> src/main.rs:2:5 | 2 | use std::io::Write; | ^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: type alias `Map` is never used --> src/main.rs:4:6 | 4 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:5:6 | 5 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:6:6 | 6 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
input! {
n: [usize; 3],
m: usize,
e: [(usize1, usize1); m],
}
let v = n.iter().sum::<usize>() + 2;
let s = v - 2;
let t = v - 1;
let mut dsu = DSU::new(v);
let mut dp = vec![[(v, 0); 3]; v];
for i in 0..n[0] {
dp[i][0] = (i, i);
}
for i in 0..n[1] {
dp[n[0] + i][1] = (i, i);
}
for i in 0..n[2] {
dp[n[0] + n[1] + i][2] = (i, i);
}
let mut edge = vec![];
for &(mut a, mut b) in e.iter() {
if a > b {
std::mem::swap(&mut a, &mut b);
}
if let Some((a, b)) = dsu.unite(a, b) {
let c = std::mem::take(&mut dp[b]);
for (a, b) in dp[a].iter_mut().zip(c.iter()) {
a.0 = a.0.min(b.0);
a.1 = a.1.max(b.1);
}
}
if b >= s {
continue;
}
let x = n
.iter()
.position(|n| {
a < *n || {
a -= *n;
false
}
})
.unwrap();
let y = n
.iter()
.position(|n| {
b < *n || {
b -= *n;
false
}
})
.unwrap();
edge.push((x, y, a, b));
}
if dsu.same(s, t) {
println!("0");
return;
}
let n_max = *n.iter().max().unwrap();
let mut ban = vec![vec![0; n_max + 2]; 3];
let mut query = vec![vec![]; 3];
let mut seg =
segment_tree::RUPQ::new(n[1] + 1, (0, n[2] + 1), |a, b| (a.0.max(b.0), a.1.min(b.1)));
for &(x, y, a, b) in edge.iter() {
if x == y {
ban[x][a + 1] += 1;
ban[x][b + 1] -= 1;
continue;
}
if x == 0 {
query[y].push((a, b));
} else {
seg.update(0, a + 1, (0, b + 1));
seg.update(a + 1, n[1] + 1, (b + 1, n[2] + 1));
}
}
for (i, ban) in ban.iter_mut().enumerate() {
for i in 1..ban.len() {
ban[i] += ban[i - 1];
}
let a = dp[dsu.root(s)];
if a[i].0 != v {
let t = a[i].1;
for j in 0..=t {
ban[j] += 1;
}
}
let b = dp[dsu.root(t)];
if b[i].0 != v {
let s = b[i].0;
for j in (s + 1)..ban.len() {
ban[j] += 1;
}
}
}
let mut range = vec![vec![0], vec![0], vec![0]];
for (query, range) in query.iter_mut().zip(range.iter_mut()) {
query.sort_by_key(|p| p.0);
for &(_, b) in query.iter() {
let v = (b + 1).max(*range.last().unwrap());
range.push(v);
}
}
let mut op = vec![];
let mut up = [0, n[1] + 2, n[2] + 2];
for i in (0..=n[0]).rev() {
if ban[0][i] > 0 {
continue;
}
for p in 1..3 {
let up = &mut up[p];
let query = &mut query[p];
let range = &mut range[p];
while query.last().map_or(false, |p| p.0 >= i) {
let (_, b) = query.pop().unwrap();
range.pop();
*up = std::cmp::min(*up, b + 1);
}
}
let (l, r) = (*range[1].last().unwrap(), up[1]);
let (d, u) = (*range[2].last().unwrap(), up[2]);
if l < r && d < u {
op.push((l, !0, d, u));
op.push((r, 1, d, u));
}
}
op.sort_by_key(|p| p.0);
let mut laz = LazySegmentTree::build(
(0..=n[2]).map(|x| if ban[2][x] > 0 { (0, 0) } else { (1, 0) }),
n[2] + 2,
R,
);
let mut x = 0;
let mut ans = 0usize;
for (pos, sign, d, u) in op {
while x < pos {
if ban[1][x] == 0 && x <= n[1] {
let (s, t) = seg.find(x);
if s < t {
laz.update(s, t, 1);
}
}
x += 1;
}
ans += sign * laz.find(d, u).1;
}
println!("{}", ans);
}
struct R;
impl TE for R {
type T = (usize, usize);
type E = usize;
fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T {
(l.0 + r.0, l.1 + r.1)
}
fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T {
(x.0, x.1 + x.0 * *f)
}
fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E {
*g + *h
}
fn e(&self) -> Self::T {
(0, 0)
}
fn id(&self) -> Self::E {
0
}
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
//---------- begin union_find ----------
pub struct DSU {
p: Vec<i32>,
}
impl DSU {
pub fn new(n: usize) -> DSU {
assert!(n < std::i32::MAX as usize);
DSU { p: vec![-1; n] }
}
pub fn init(&mut self) {
self.p.iter_mut().for_each(|p| *p = -1);
}
pub fn root(&self, mut x: usize) -> usize {
assert!(x < self.p.len());
while self.p[x] >= 0 {
x = self.p[x] as usize;
}
x
}
pub fn same(&self, x: usize, y: usize) -> bool {
assert!(x < self.p.len() && y < self.p.len());
self.root(x) == self.root(y)
}
pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
assert!(x < self.p.len() && y < self.p.len());
let mut x = self.root(x);
let mut y = self.root(y);
if x == y {
return None;
}
if self.p[x] > self.p[y] {
std::mem::swap(&mut x, &mut y);
}
self.p[x] += self.p[y];
self.p[y] = x as i32;
Some((x, y))
}
pub fn parent(&self, x: usize) -> Option<usize> {
assert!(x < self.p.len());
let p = self.p[x];
if p >= 0 {
Some(p as usize)
} else {
None
}
}
pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
where
F: FnMut(usize),
{
while let Some(p) = self.parent(x) {
f(x);
x = p;
}
x
}
pub fn size(&self, x: usize) -> usize {
assert!(x < self.p.len());
let r = self.root(x);
(-self.p[r]) as usize
}
}
//---------- end union_find ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
fn chmin(&mut self, x: Self) -> bool;
fn chmax(&mut self, x: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn chmin(&mut self, x: Self) -> bool {
*self > x && {
*self = x;
true
}
}
fn chmax(&mut self, x: Self) -> bool {
*self < x && {
*self = x;
true
}
}
}
// ---------- end chmin, chmax ----------
// ---------- begin SegmentTree Range update Point query ----------
mod segment_tree {
pub struct RUPQ<T, F> {
size: usize,
bit: usize,
data: Vec<T>,
e: T,
op: F,
}
impl<T, F> RUPQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(size: usize, e: T, op: F) -> Self {
let size = size.next_power_of_two();
let bit = size.trailing_zeros() as usize;
Self {
size,
bit,
data: vec![e.clone(); 2 * size],
e,
op,
}
}
pub fn find(&self, x: usize) -> T {
assert!(x < self.size);
let mut x = x + self.size;
let mut ans = self.data[x].clone();
while x > 1 {
x >>= 1;
ans = (self.op)(&ans, &self.data[x]);
}
ans
}
fn propagate(&mut self, x: usize) {
let f = std::mem::replace(&mut self.data[x], self.e.clone());
self.data[2 * x] = (self.op)(&self.data[2 * x], &f);
self.data[2 * x + 1] = (self.op)(&self.data[2 * x + 1], &f);
}
pub fn update(&mut self, l: usize, r: usize, f: T) {
assert!(l <= r && r <= self.size);
if l == r {
return;
}
let mut l = l + self.size;
let mut r = r + self.size;
for i in (1..=self.bit).rev() {
if (l >> i) << i != l {
self.propagate(l >> i);
}
if (r >> i) << i != r {
self.propagate((r - 1) >> i);
}
}
while l < r {
if l & 1 == 1 {
self.data[l] = (self.op)(&self.data[l], &f);
l += 1;
}
if r & 1 == 1 {
r -= 1;
self.data[r] = (self.op)(&self.data[r], &f);
}
l >>= 1;
r >>= 1;
}
}
}
}
// ---------- end SegmentTree Range update Point query ----------
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
n: usize,
size: usize,
data: Vec<T>,
e: T,
op: F,
}
impl<T, F> SegmentTreePURQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(n: usize, e: T, op: F) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let data = vec![e.clone(); 2 * size];
SegmentTreePURQ {
n,
size,
data,
e,
op,
}
}
pub fn update_tmp(&mut self, x: usize, v: T) {
assert!(x < self.n);
self.data[x + self.size] = v;
}
pub fn update_all(&mut self) {
for i in (1..self.size).rev() {
self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
}
}
pub fn update(&mut self, x: usize, v: T) {
assert!(x < self.n);
let mut x = x + self.size;
self.data[x] = v;
x >>= 1;
while x > 0 {
self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
x >>= 1;
}
}
pub fn find(&self, l: usize, r: usize) -> T {
assert!(l <= r && r <= self.n);
if l == r {
return self.e.clone();
}
let mut l = self.size + l;
let mut r = self.size + r;
let mut x = self.e.clone();
let mut y = self.e.clone();
while l < r {
if l & 1 == 1 {
x = (self.op)(&x, &self.data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
y = (self.op)(&self.data[r], &y);
}
l >>= 1;
r >>= 1;
}
(self.op)(&x, &y)
}
pub fn max_right<P>(&self, l: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(l <= self.n);
assert!(f(&self.e));
if l == self.n {
return self.n;
}
let mut l = l + self.size;
let mut sum = self.e.clone();
while {
l >>= l.trailing_zeros();
let v = (self.op)(&sum, &self.data[l]);
if !f(&v) {
while l < self.size {
l <<= 1;
let v = (self.op)(&sum, &self.data[l]);
if f(&v) {
sum = v;
l += 1;
}
}
return l - self.size;
}
sum = v;
l += 1;
l.count_ones() > 1
} {}
self.n
}
pub fn min_left<P>(&self, r: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(r <= self.n);
assert!(f(&self.e));
if r == 0 {
return 0;
}
let mut r = r + self.size;
let mut sum = self.e.clone();
while {
r -= 1;
while r > 1 && r & 1 == 1 {
r >>= 1;
}
let v = (self.op)(&self.data[r], &sum);
if !f(&v) {
while r < self.size {
r = 2 * r + 1;
let v = (self.op)(&self.data[r], &sum);
if f(&v) {
sum = v;
r -= 1;
}
}
return r + 1 - self.size;
}
sum = v;
(r & (!r + 1)) != r
} {}
0
}
}
// ---------- end segment tree Point Update Range Query ----------
// ---------- begin Lazy Segment Tree ----------
pub trait TE {
type T: Clone;
type E: Clone;
fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T;
fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T;
fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E;
fn e(&self) -> Self::T;
fn id(&self) -> Self::E;
}
pub struct LazySegmentTree<R: TE> {
n: usize,
size: usize,
bit: u32,
op: R,
data: Vec<(R::T, R::E)>,
}
impl<R: TE> LazySegmentTree<R> {
pub fn new(n: usize, op: R) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let bit = size.trailing_zeros();
let data = vec![(op.e(), op.id()); 2 * size];
Self {
n,
size,
bit,
op,
data,
}
}
pub fn build<I>(init: I, n: usize, op: R) -> Self
where
I: Iterator<Item = R::T>,
{
let mut seg = Self::new(n, op);
for (data, ini) in seg.data[seg.size..].iter_mut().zip(init) {
data.0 = ini;
}
for i in (1..seg.size).rev() {
seg.pull(i);
}
seg
}
pub fn update(&mut self, l: usize, r: usize, f: R::E) {
assert!(l <= r && r <= self.n);
if l == r {
return;
}
self.push_range(l, r);
let mut s = l + self.size;
let mut t = r + self.size;
while s < t {
if s & 1 == 1 {
self.apply(s, &f);
s += 1;
}
if t & 1 == 1 {
t -= 1;
self.apply(t, &f);
}
s >>= 1;
t >>= 1;
}
let l = l + self.size;
let r = r + self.size;
for k in 1..=self.bit {
if (l >> k) << k != l {
self.pull(l >> k);
}
if (r >> k) << k != r {
self.pull((r - 1) >> k);
}
}
}
pub fn find(&mut self, l: usize, r: usize) -> R::T {
assert!(l <= r && r <= self.n);
if l == r {
return self.op.e();
}
self.push_range(l, r);
let mut l = l + self.size;
let mut r = r + self.size;
let mut p = self.op.e();
let mut q = self.op.e();
while l < r {
if l & 1 == 1 {
p = self.op.fold(&p, &self.data[l].0);
l += 1;
}
if r & 1 == 1 {
r -= 1;
q = self.op.fold(&self.data[r].0, &q);
}
l >>= 1;
r >>= 1;
}
self.op.fold(&p, &q)
}
pub fn set_at(&mut self, x: usize, v: R::T) {
assert!(x < self.n);
let x = x + self.size;
for k in (1..=self.bit).rev() {
self.push(x >> k);
}
self.data[x].0 = v;
for k in 1..=self.bit {
self.pull(x >> k);
}
}
fn push_range(&mut self, l: usize, r: usize) {
let l = l + self.size;
let r = r + self.size;
for k in (1..=self.bit).rev() {
if (l >> k) << k != l {
self.push(l >> k);
}
if (r >> k) << k != r {
self.push((r - 1) >> k);
}
}
}
fn apply(&mut self, x: usize, f: &R::E) {
self.data[x].0 = self.op.eval(&self.data[x].0, f);
self.data[x].1 = self.op.merge(&self.data[x].1, f);
}
fn push(&mut self, x: usize) {
let f = std::mem::replace(&mut self.data[x].1, self.op.id());
self.apply(2 * x, &f);
self.apply(2 * x + 1, &f);
}
fn pull(&mut self, x: usize) {
self.data[x].0 = self.op.fold(&self.data[2 * x].0, &self.data[2 * x + 1].0);
}
}
// ---------- end Lazy Segment Tree ----------