提出 #27915835

---

ソースコード 拡げる

#![allow(non_snake_case, unused)]

use proconio::{*, marker::*, source::line::LineSource};
use rand::prelude::*;
use std::io::{BufReader, Stdin};

pub trait SetMinMax {
	fn setmin(&mut self, v: Self) -> bool;
	fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T where T: PartialOrd {
	fn setmin(&mut self, v: T) -> bool {
		*self > v && { *self = v; true }
	}
	fn setmax(&mut self, v: T) -> bool {
		*self < v && { *self = v; true }
	}
}

#[macro_export]
macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

pub fn get_time() -> f64 {
	static mut STIME: f64 = -1.0;
	let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
	let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
	unsafe {
		if STIME < 0.0 {
			STIME = ms;
		}
		ms - STIME
	}
}

use std::cell::Cell;
use std::collections::BinaryHeap;

#[derive(Clone, Debug)]
pub struct UnionFind {
	/// size / parent
	ps: Vec<Cell<usize>>,
	pub is_root: Vec<bool>
}

impl UnionFind {
	pub fn new(n: usize) -> UnionFind {
		UnionFind { ps: vec![Cell::new(1); n], is_root: vec![true; n] }
	}
	pub fn find(&self, x: usize) -> usize {
		if self.is_root[x] { x }
		else {
			let p = self.find(self.ps[x].get());
			self.ps[x].set(p);
			p
		}
	}
	pub fn unite(&mut self, x: usize, y: usize) {
		let mut x = self.find(x);
		let mut y = self.find(y);
		if x == y { return }
		if self.ps[x].get() < self.ps[y].get() {
			::std::mem::swap(&mut x, &mut y);
		}
		*self.ps[x].get_mut() += self.ps[y].get();
		self.ps[y].set(x);
		self.is_root[y] = false;
	}
	pub fn same(&self, x: usize, y: usize) -> bool {
		self.find(x) == self.find(y)
	}
	pub fn size(&self, x: usize) -> usize {
		self.ps[self.find(x)].get()
	}
}

const K: usize = 5;
pub const N: usize = 400;
pub const M: usize = (N - 1) * K;

pub struct Input {
	ps: Vec<(i32, i32)>,
	es: Vec<(usize, usize, i32, i32)>
}

fn dist2((x1, y1): (i32, i32), (x2, y2): (i32, i32)) -> i32 {
	(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
}

fn dist(p1: (i32, i32), p2: (i32, i32)) -> i32 {
	f64::sqrt(dist2(p1, p2) as f64).round() as i32
}

fn read_input(stdin: &mut LineSource<BufReader<Stdin>>) -> Input {
	input! {
		from stdin,
		ps: [(i32, i32); N],
		es: [(usize, usize); M],
	}
	let es = es.into_iter().map(|(u, v)| {
		let d = dist(ps[u], ps[v]);
		(u, v, d, d * 3)
	}).collect();
	Input {
		ps,
		es,
	}
}

// 与えられた辺集合から1本選ぶ場合の長さの期待値をDPで最小化してcを選ぶ方が良いか判定
fn dp2(input: &Input, cut: &Vec<usize>, c: i32) -> bool {
	let n = cut.len();
	let mut dp = vec![0.0; n];
	dp[n - 1] = (input.es[cut[n - 1]].2 + input.es[cut[n - 1]].3) as f64 / 2.0;
	for k in (0..n-1).rev() {
		let L = input.es[cut[k]].2 as f64;
		let R = input.es[cut[k]].3 as f64;
		if dp[k + 1] <= L {
			dp[k] = dp[k + 1];
		} else if R <= dp[k + 1] {
			dp[k] = (L + R) / 2.0;
		} else {
			let p = dp[k + 1].floor();
			dp[k] = ((L + p) * (p - L + 1.0) / 2.0 + dp[k + 1] * (R - p)) / (R - L + 1.0);
		}
	}
	c as f64 <= dp[1]
}

// 与えられた3種類の辺集合から異なる種類の2辺を選ぶ場合の長さの期待値をDPで最小化してcを選ぶ方が良いか判定
fn dp3(input: &Input, cut: &Vec<(usize, i32)>, c: i32) -> bool {
	let n = cut.len();
	let mut dp = mat![0.0f64; n + 1; 8];
	for i in 0..8 {
		if usize::count_ones(i) >= 2 {
			dp[n][i] = 1e9;
		}
	}
	for k in (0..n).rev() {
		let (e, p) = cut[k];
		for i in 0..8 {
			if i >> p & 1 != 0 {
				let i2 = i ^ (1 << p);
				let L = dp[k + 1][i2] + input.es[e].2 as f64;
				let R = dp[k + 1][i2] + input.es[e].3 as f64;
				if dp[k + 1][i] <= L {
					dp[k][i] = dp[k + 1][i];
				} else if R <= dp[k + 1][i] {
					dp[k][i] = (L + R) / 2.0;
				} else {
					let p = dp[k + 1][i].floor();
					dp[k][i] = ((L + p) * (p - L + 1.0) / 2.0 + dp[k + 1][i] * (R - p)) / (R - L + 1.0);
				}
			} else {
				dp[k][i] = dp[k + 1][i];
			}
		}
	}
	dp[0][7 ^ (1 << cut[0].1)] + c as f64 <= dp[1][7]
}

const REP: usize = 1000;

// DPで判定に失敗したときだけモンテカルロ

fn solve(input: &Input, mut stdin: LineSource<BufReader<Stdin>>) {
	let mut rng = rand_pcg::Pcg64Mcg::seed_from_u64(8391028707);
	let mut es = mat![(0, 0, 0, 0); REP; M];
	for i in 0..REP {
		for e in 0..M {
			es[i][e] = (rng.gen_range(input.es[e].2 * 113 / 100, input.es[e].3 - input.es[e].2 * 13 / 100 + 1), e, input.es[e].0, input.es[e].1);
		}
		es[i].sort();
	}
	let mut uf = UnionFind::new(N);
	let mut out = vec![0; M];
	let mut cost = 0;
	for f in 0..M {
		input! {
			from &mut stdin,
			c: i32,
		}
		let (s, t, _, _) = input.es[f];
		if !uf.same(s, t) {
			let mut uf2 = uf.clone();
			for e in f+1..M {
				// 期待値の小さい辺がカットに含まれると判定に失敗するので先に縮約 (3-way cutでの判定時に確実に失敗する条件はよく分からないのでちょっと余裕を持たせた)
				if (input.es[e].2 + input.es[e].3) as f64 / 2.0 + 10.0 < c as f64 {
					uf2.unite(input.es[e].0, input.es[e].1);
				}
			}
			if !uf2.same(s, t) {
				// 高速化のため、縮約後のグラフを構築
				let mut id = vec![!0; N];
				let mut m = 0;
				for i in 0..N {
					if id[uf2.find(i)] == !0 {
						id[uf2.find(i)] = m;
						m += 1;
					}
					id[i] = id[uf2.find(i)];
				}
				eprintln!("{}: {}", f, m);
				let mut g = vec![vec![]; N];
				for e in f..M {
					let i = id[input.es[e].0];
					let j = id[input.es[e].1];
					if i != j {
						g[i].push((j, e));
						g[j].push((i, e));
					}
				}
				let (s, t) = (id[s], id[t]);
				for iter in 0..50 {
					// ランダム重みでprim法を走らせてカットを構築
					let mut que = BinaryHeap::new();
					let mut min = vec![(1000000000, -1i32); m];
					let mut fixed = vec![false; m];
					let mut cut = vec![vec![]; 2];
					let mut tmp = vec![];
					que.push((0, s));
					que.push((0, t));
					min[s] = (0, 0);
					min[t] = (0, 1);
					while let Some((_, u)) = que.pop() {
						if fixed[u] {
							continue;
						}
						fixed[u] = true;
						let r = min[u].1;
						{ // 2-way cut での判定
							let cut = &mut cut[r as usize];
							tmp.clear();
							let mut x = 0;
							let mut y = 0;
							while x < cut.len() && y < g[u].len() {
								if cut[x] == g[u][y].1 {
									x += 1;
									y += 1;
								} else if cut[x] < g[u][y].1 {
									tmp.push(cut[x]);
									x += 1;
								} else {
									tmp.push(g[u][y].1);
									y += 1;
								}
							}
							while x < cut.len() {
								tmp.push(cut[x]);
								x += 1;
							}
							while y < g[u].len() {
								tmp.push(g[u][y].1);
								y += 1;
							}
							std::mem::swap(cut, &mut tmp);
							let cut0 = cut.iter().filter(|&&e| fixed[id[input.es[e].0]] && fixed[id[input.es[e].1]]).cloned().collect::<Vec<_>>();
							if cut0.len() >= 2 && !dp2(input, &cut0, c) { // この先ずっとカットに含まれる辺のみで判定に失敗したら枝刈り
								break;
							}
							if cut.len() == 1 || dp2(input, &cut, c) { // cutから1本以上選ぶ必要が有り、現在の辺を選ばなかった場合の期待値の方が大きいなら選んだ方がお得
								out[f] = 1;
								break;
							}
						}
						if cut[0].len() > 0 && cut[1].len() > 0 { // 3-way cut での判定
							let mut cut2 = vec![];
							let mut x = 0;
							let mut y = 0;
							while x < cut[0].len() && y < cut[1].len() {
								if cut[0][x] == cut[1][y] {
									cut2.push((cut[0][x], 0));
									x += 1;
									y += 1;
								} else if cut[0][x] < cut[1][y] {
									cut2.push((cut[0][x], 1));
									x += 1;
								} else {
									cut2.push((cut[1][y], 2));
									y += 1;
								}
							}
							while x < cut[0].len() {
								cut2.push((cut[0][x], 1));
								x += 1;
							}
							while y < cut[1].len() {
								cut2.push((cut[1][y], 2));
								y += 1;
							}
							if dp3(input, &cut2, c) { // cutから2本以上選ぶ必要が有り、現在の辺を選ばなかった場合の期待値の方が大きいなら選んだ方がお得
								out[f] = 1;
								eprintln!("3-way cut");
								break;
							}
						}
						for &(v, e) in &g[u] {
							if fixed[v] {
								continue;
							}
							let d = rng.gen_range(input.es[e].2, input.es[e].3 + 1);
							if min[v].0 > d {
								min[v] = (d, r);
								que.push((-d, v));
							}
						}
					}
					if out[f] == 1 {
						break;
					}
				}
			}
			if out[f] == 0 {
				let (s, t) = (uf.find(input.es[f].0), uf.find(input.es[f].1));
				let mut avg = 0;
				for i in 0..REP {
					let mut uf2 = uf.clone();
					for &(d, e, u, v) in &es[i] {
						if e > f && !uf2.same(u, v) {
							uf2.unite(u, v);
							if uf2.same(s, t) {
								avg += d - c;
								break;
							}
						}
					}
					if !uf2.same(s, t) {
						avg = 1000000000;
						break;
					}
					if avg.abs() > 1000 {
						break;
					}
				}
				if avg >= 0 {
					out[f] = 1;
				}
			}
		}
		if out[f] == 1 {
			uf.unite(s, t);
			cost += c;
		}
		println!("{}", out[f]);
	}
	eprintln!("cost = {}", cost);
	assert_eq!(out.iter().sum::<usize>(), N - 1);
}

fn main() {
	get_time();
	let mut stdin = proconio::source::line::LineSource::new(std::io::BufReader::new(std::io::stdin()));
	let input = read_input(&mut stdin);
	solve(&input, stdin);
	eprintln!("Time = {:.3}", get_time());
}

提出情報

ジャッジ結果