QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196580 | #7513. Palindromic Beads | ucup-team296 | TL | 1ms | 2688kb | Rust | 30.7kb | 2023-10-01 19:46:01 | 2023-10-01 19:46:01 |
Judging History
answer
pub mod solution {
//{"name":"b","group":"Manual","url":"","interactive":false,"timeLimit":2000,"tests":[{"input":"","output":""},{"input":"","output":""}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"b"}}}
use std::cmp::Reverse;
use std::ops::Range;
use crate::algo_lib::io::output::output;
use crate::algo_lib::io::task_io_settings::TaskIoType;
use crate::algo_lib::io::task_runner::run_task;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::task_io_settings::TaskIoSettings;
use crate::algo_lib::misc::min_max::UpdateMinMax;
use crate::algo_lib::misc::rec_function::Callable2;
use crate::algo_lib::misc::rec_function::Callable3;
use crate::algo_lib::misc::rec_function::RecursiveFunction2;
use crate::algo_lib::misc::rec_function::RecursiveFunction3;
use crate::algo_lib::misc::vec_apply_delta::ApplyDelta;
use crate::algo_lib::seg_trees::hld::Hld;
#[allow(unused)]
use crate::dbg;
use crate::out;
use crate::out_line;
#[derive(Clone, Copy, Default, Debug)]
pub struct VertexInfo {
pub pos: usize,
// range is [pos..max_subtree_pos)
pub max_subtree_pos: usize,
pub parent: usize,
pub height: usize,
}
impl VertexInfo {
pub fn range(&self) -> Range<usize> {
self.pos..self.max_subtree_pos
}
}
#[derive(Debug)]
pub struct DfsOrder {
pub order: Vec<usize>,
pub info: Vec<VertexInfo>,
}
impl DfsOrder {
pub fn new(g: &[Vec<usize>], root: usize) -> Self {
let n = g.len();
let mut order = vec![];
let mut info = vec![VertexInfo::default(); n];
RecursiveFunction3::new(|f, v: usize, p: usize, h: usize| {
order.push(v);
info[v].pos = order.len() - 1;
info[v].max_subtree_pos = order.len();
info[v].parent = p;
info[v].height = h;
for &to in g[v].iter() {
if to != p {
f.call(to, v, h + 1);
let max_subtree_pos = info[to].max_subtree_pos;
info[v].max_subtree_pos.update_max(max_subtree_pos);
}
}
})
.call(root, root, 0);
assert_eq!(order.len(), n);
Self { order, info }
}
pub fn is_in_subtree_of(&self, v: usize, anc: usize) -> bool {
self.info[anc].pos <= self.info[v].pos && self.info[v].pos < self.info[anc].max_subtree_pos
}
}
#[derive(Clone, Copy, Debug)]
struct Color {
min_v: usize,
max_v: usize,
dist: usize,
}
struct Point {
x: usize,
y: usize,
value: usize,
}
struct SlowSegTree2D {
nodes: Vec<Point>,
}
impl SlowSegTree2D {
pub fn new() -> Self {
Self { nodes: vec![] }
}
pub fn get_max(&self, x_range: Range<usize>, y_range: Range<usize>) -> usize {
let mut res = 0;
for p in self.nodes.iter() {
if x_range.contains(&p.x) && y_range.contains(&p.y) {
res.update_max(p.value);
}
}
res
}
pub fn add(&mut self, x: usize, y: usize, value: usize) {
self.nodes.push(Point { x, y, value });
}
}
fn solve(input: &mut Input, _test_case: usize) {
let n = input.usize();
let colors = input.vec::<usize>(n).sub_from_all(1);
let mut g = vec![vec![]; n];
for _ in 0..n - 1 {
let u = input.usize() - 1;
let v = input.usize() - 1;
g[u].push(v);
g[v].push(u);
}
let hld = Hld::new(g.clone(), 0);
let dfs_order = DfsOrder::new(&g, 0);
let mut by_color = vec![vec![]; n];
for v in 0..n {
by_color[colors[v]].push(v);
}
let mut pairs = vec![];
for color in 0..colors.len() {
if by_color[color].len() == 2 {
let (v, u) = (by_color[color][0], by_color[color][1]);
let lca = hld.lca(v, u);
let dist = dfs_order.info[v].height + dfs_order.info[u].height
- 2 * dfs_order.info[lca].height;
let pos1 = dfs_order.info[v].pos;
let pos2 = dfs_order.info[u].pos;
let (min_v, max_v) = if pos1 < pos2 { (v, u) } else { (u, v) };
pairs.push(Color { min_v, max_v, dist })
}
}
let mut st = SlowSegTree2D::new();
pairs.sort_by_key(|p| Reverse(p.dist));
let mut glob_res = 1;
for pair in pairs.iter() {
let (min_v, max_v) = (pair.min_v, pair.max_v);
let mut res;
if dfs_order.is_in_subtree_of(max_v, min_v) {
res = st.get_max(0..dfs_order.info[min_v].pos, dfs_order.info[max_v].range());
res.update_max(st.get_max(
dfs_order.info[max_v].range(),
dfs_order.info[min_v].max_subtree_pos..n,
));
for &to in g[min_v].iter() {
if !dfs_order.is_in_subtree_of(max_v, to) && dfs_order.info[min_v].parent != to {
let r1 = dfs_order.info[max_v].range();
let r2 = dfs_order.info[to].range();
if r1.start < r2.start {
res.update_max(st.get_max(r1, r2));
} else {
res.update_max(st.get_max(r2, r1));
}
}
}
} else {
res = st.get_max(dfs_order.info[min_v].range(), dfs_order.info[max_v].range());
}
let mut update_res = res + 2;
st.add(
dfs_order.info[min_v].pos,
dfs_order.info[max_v].pos,
update_res,
);
if dfs_order.info[max_v].parent != min_v {
update_res += 1;
}
glob_res.update_max(update_res);
}
out_line!(glob_res);
}
pub(crate) fn run(mut input: Input) -> bool {
solve(&mut input, 1);
output().flush();
true
}
#[allow(unused)]
pub fn submit() -> bool {
let io = TaskIoSettings {
is_interactive: false,
input: TaskIoType::Std,
output: TaskIoType::Std,
};
run_task(io, run)
}
}
pub mod algo_lib {
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;
pub struct Input {
input: Box<dyn Read>,
buf: Vec<u8>,
at: usize,
buf_read: usize,
}
macro_rules! read_integer_fun {
($t:ident) => {
#[allow(unused)]
pub fn $t(&mut self) -> $t {
self.read_integer()
}
};
}
impl Input {
const DEFAULT_BUF_SIZE: usize = 4096;
///
/// Using with stdin:
/// ```no_run
/// use algo_lib::io::input::Input;
/// let stdin = std::io::stdin();
/// let input = Input::new(Box::new(stdin));
/// ```
///
/// For read files use ``new_file`` instead.
///
///
pub fn new(input: Box<dyn Read>) -> Self {
Self {
input,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
}
}
pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new(Box::new(file))
}
pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
Self {
input,
buf: vec![0; buf_size],
at: 0,
buf_read: 0,
}
}
pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new_with_size(Box::new(file), buf_size)
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
Some(self.buf[self.at])
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !char::from(b).is_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if char::from(c).is_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() {
None
} else {
Some(res)
}
}
//noinspection RsSelfConvention
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn has_more_elements(&mut self) -> bool {
!self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.read());
}
res
}
pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.string());
}
res
}
pub fn read_line(&mut self) -> String {
let mut res = String::new();
while let Some(c) = self.get() {
if c == b'\n' {
break;
}
if c == b'\r' {
if self.peek() == Some(b'\n') {
self.get();
}
break;
}
res.push(c.into());
}
res
}
#[allow(clippy::should_implement_trait)]
pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
InputIterator {
input: self,
phantom: Default::default(),
}
}
fn read_integer<T: FromStr>(&mut self) -> T
where
<T as FromStr>::Err: Debug,
{
let res = self.read_string();
res.parse::<T>().unwrap()
}
fn read_string(&mut self) -> String {
match self.next_token() {
None => {
panic!("Input exhausted");
}
Some(res) => unsafe { String::from_utf8_unchecked(res) },
}
}
pub fn string_as_string(&mut self) -> String {
self.read_string()
}
pub fn string(&mut self) -> Vec<u8> {
self.read_string().into_bytes()
}
fn read_char(&mut self) -> char {
self.skip_whitespace();
self.get().unwrap().into()
}
fn read_float(&mut self) -> f64 {
self.read_string().parse().unwrap()
}
pub fn f64(&mut self) -> f64 {
self.read_float()
}
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
read_integer_fun!(i32);
read_integer_fun!(i64);
read_integer_fun!(i128);
read_integer_fun!(u32);
read_integer_fun!(u64);
read_integer_fun!(usize);
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for String {
fn read(input: &mut Input) -> Self {
input.read_string()
}
}
impl Readable for char {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl Readable for f64 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl Readable for f32 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.vec(size)
}
}
pub struct InputIterator<T: Readable> {
input: Input,
phantom: PhantomData<T>,
}
impl<T: Readable> Iterator for InputIterator<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.input.skip_whitespace();
self.input.peek().map(|_| self.input.read())
}
}
macro_rules! read_integer {
($t:ident) => {
impl Readable for $t {
fn read(input: &mut Input) -> Self {
input.read_integer()
}
}
};
}
read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;
pub struct Output {
output: Box<dyn Write>,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
}
impl Output {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: false,
}
}
pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: true,
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.at = 0;
self.output.flush().expect("Couldn't flush output");
}
}
pub fn print<T: Writable>(&mut self, s: &T) {
s.write(self);
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
for i in arg {
i.write(self);
self.put(b'\n');
}
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
}
impl Write for Output {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
if self.auto_flush {
self.flush();
}
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter_ref(self.iter());
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self[..].write(output);
}
}
macro_rules! write_to_string {
($t:ident) => {
impl Writable for $t {
fn write(&self, output: &mut Output) {
self.to_string().write(output);
}
}
};
}
write_to_string!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);
impl<T: Writable, U: Writable> Writable for (T, U) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
}
}
impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
output.put(b' ');
self.2.write(output);
}
}
pub static mut OUTPUT: Option<Output> = None;
pub fn set_global_output_to_stdout() {
unsafe {
OUTPUT = Some(Output::new(Box::new(std::io::stdout())));
}
}
pub fn set_global_output_to_file(path: &str) {
unsafe {
let out_file =
std::fs::File::create(path).unwrap_or_else(|_| panic!("Can't create file {}", path));
OUTPUT = Some(Output::new(Box::new(out_file)));
}
}
pub fn set_global_output_to_none() {
unsafe {
match &mut OUTPUT {
None => {}
Some(output) => output.flush(),
}
OUTPUT = None;
}
}
pub fn output() -> &'static mut Output {
unsafe {
match &mut OUTPUT {
None => {
panic!("Global output wasn't initialized");
}
Some(output) => output,
}
}
}
#[macro_export]
macro_rules! out {
($first: expr $(,$args:expr )*) => {
output().print(&$first);
$(output().put(b' ');
output().print(&$args);
)*
output().maybe_flush();
}
}
#[macro_export]
macro_rules! out_line {
($first: expr $(, $args:expr )* ) => {
{
out!($first $(,$args)*);
output().put(b'\n');
output().maybe_flush();
}
};
() => {
{
output().put(b'\n');
output().maybe_flush();
}
};
}
}
pub mod task_io_settings {
pub enum TaskIoType {
Std,
File(String),
}
pub struct TaskIoSettings {
pub is_interactive: bool,
pub input: TaskIoType,
pub output: TaskIoType,
}
}
pub mod task_runner {
use std::io::Write;
use super::input::Input;
use super::output::Output;
use super::output::OUTPUT;
use super::task_io_settings::TaskIoSettings;
use super::task_io_settings::TaskIoType;
pub fn run_task<Res>(io: TaskIoSettings, run: impl FnOnce(Input) -> Res) -> Res {
let output: Box<dyn Write> = match io.output {
TaskIoType::Std => Box::new(std::io::stdout()),
TaskIoType::File(file) => {
let out_file = std::fs::File::create(file).unwrap();
Box::new(out_file)
}
};
unsafe {
OUTPUT = Some(Output::new(output));
}
let input = match io.input {
TaskIoType::Std => {
let sin = std::io::stdin();
Input::new(Box::new(sin))
}
TaskIoType::File(file) => Input::new_file(file),
};
run(input)
}
}
}
pub mod misc {
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
($first_val:expr, $($val:expr),+ $(,)?) => {
eprint!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val);
($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
eprintln!();
};
($first_val:expr) => {
eprintln!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val)
};
}
}
pub mod min_max {
pub trait UpdateMinMax: PartialOrd + Sized {
#[inline(always)]
fn update_min(&mut self, other: Self) -> bool {
if other < *self {
*self = other;
true
} else {
false
}
}
#[inline(always)]
fn update_max(&mut self, other: Self) -> bool {
if other > *self {
*self = other;
true
} else {
false
}
}
}
impl<T: PartialOrd + Sized> UpdateMinMax for T {}
pub trait FindMinMaxPos {
fn index_of_min(&self) -> usize;
fn index_of_max(&self) -> usize;
}
impl<T: PartialOrd> FindMinMaxPos for [T] {
fn index_of_min(&self) -> usize {
let mut pos_of_best = 0;
for (idx, val) in self.iter().enumerate().skip(1) {
if val < &self[pos_of_best] {
pos_of_best = idx;
}
}
pos_of_best
}
fn index_of_max(&self) -> usize {
let mut pos_of_best = 0;
for (idx, val) in self.iter().enumerate().skip(1) {
if val > &self[pos_of_best] {
pos_of_best = idx;
}
}
pos_of_best
}
}
pub fn index_of_min_by<T, F>(n: usize, f: F) -> usize
where
T: PartialOrd,
F: Fn(usize) -> T,
{
assert!(n > 0);
let mut best_idx = 0;
let mut best_val = f(0);
for idx in 1..n {
let cur_val = f(idx);
if cur_val < best_val {
best_val = cur_val;
best_idx = idx;
}
}
best_idx
}
pub fn index_of_max_by<T, F>(n: usize, f: F) -> usize
where
T: PartialOrd,
F: Fn(usize) -> T,
{
assert!(n > 0);
let mut best_idx = 0;
let mut best_val = f(0);
for idx in 1..n {
let cur_val = f(idx);
if cur_val > best_val {
best_val = cur_val;
best_idx = idx;
}
}
best_idx
}
}
pub mod num_traits {
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Sub;
use std::ops::SubAssign;
pub trait HasConstants<T> {
const MAX: T;
const MIN: T;
const ZERO: T;
const ONE: T;
const TWO: T;
}
pub trait ConvSimple<T> {
fn from_i32(val: i32) -> T;
fn to_i32(self) -> i32;
fn to_f64(self) -> f64;
}
pub trait Signum {
fn signum(&self) -> i32;
}
pub trait Number:
Copy
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ PartialOrd
+ PartialEq
+ HasConstants<Self>
+ Default
+ Debug
+ Sized
+ ConvSimple<Self>
{
}
impl<
T: Copy
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ PartialOrd
+ PartialEq
+ HasConstants<Self>
+ Default
+ Debug
+ Sized
+ ConvSimple<Self>,
> Number for T
{
}
macro_rules! has_constants_impl {
($t: ident) => {
impl HasConstants<$t> for $t {
// TODO: remove `std` for new rust version..
const MAX: $t = std::$t::MAX;
const MIN: $t = std::$t::MIN;
const ZERO: $t = 0;
const ONE: $t = 1;
const TWO: $t = 2;
}
impl ConvSimple<$t> for $t {
fn from_i32(val: i32) -> $t {
val as $t
}
fn to_i32(self) -> i32 {
self as i32
}
fn to_f64(self) -> f64 {
self as f64
}
}
};
}
has_constants_impl!(i32);
has_constants_impl!(i64);
has_constants_impl!(i128);
has_constants_impl!(u32);
has_constants_impl!(u64);
has_constants_impl!(u128);
has_constants_impl!(usize);
has_constants_impl!(u8);
impl ConvSimple<Self> for f64 {
fn from_i32(val: i32) -> Self {
val as f64
}
fn to_i32(self) -> i32 {
self as i32
}
fn to_f64(self) -> f64 {
self
}
}
impl HasConstants<Self> for f64 {
const MAX: Self = Self::MAX;
const MIN: Self = -Self::MAX;
const ZERO: Self = 0.0;
const ONE: Self = 1.0;
const TWO: Self = 2.0;
}
impl<T: Number + Ord> Signum for T {
fn signum(&self) -> i32 {
match self.cmp(&T::ZERO) {
Ordering::Greater => 1,
Ordering::Less => -1,
Ordering::Equal => 0,
}
}
}
}
pub mod rec_function {
// Copied from https://github.com/EgorKulikov/rust_algo/blob/master/algo_lib/src/misc/recursive_function.rs
use std::marker::PhantomData;
macro_rules! recursive_function {
($name: ident, $trait: ident, ($($type: ident $arg: ident,)*)) => {
pub trait $trait<$($type, )*Output> {
fn call(&mut self, $($arg: $type,)*) -> Output;
}
pub struct $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
f: F,
$($arg: PhantomData<$type>,
)*
phantom_output: PhantomData<Output>,
}
impl<F, $($type, )*Output> $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
pub fn new(f: F) -> Self {
Self {
f,
$($arg: Default::default(),
)*
phantom_output: Default::default(),
}
}
}
impl<F, $($type, )*Output> $trait<$($type, )*Output> for $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
fn call(&mut self, $($arg: $type,)*) -> Output {
let const_ptr = &self.f as *const F;
let mut_ptr = const_ptr as *mut F;
unsafe { (&mut *mut_ptr)(self, $($arg, )*) }
}
}
}
}
recursive_function!(RecursiveFunction0, Callable0, ());
recursive_function!(RecursiveFunction, Callable, (Arg arg,));
recursive_function!(RecursiveFunction2, Callable2, (Arg1 arg1, Arg2 arg2,));
recursive_function!(RecursiveFunction3, Callable3, (Arg1 arg1, Arg2 arg2, Arg3 arg3,));
recursive_function!(RecursiveFunction4, Callable4, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4,));
recursive_function!(RecursiveFunction5, Callable5, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5,));
recursive_function!(RecursiveFunction6, Callable6, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6,));
recursive_function!(RecursiveFunction7, Callable7, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7,));
recursive_function!(RecursiveFunction8, Callable8, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8,));
recursive_function!(RecursiveFunction9, Callable9, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8, Arg9 arg9,));
}
pub mod vec_apply_delta {
use crate::algo_lib::misc::num_traits::Number;
pub trait ApplyDelta<T> {
fn add_to_all(self, delta: T) -> Self;
fn sub_from_all(self, sub: T) -> Self;
}
impl<T> ApplyDelta<T> for Vec<T>
where
T: Number,
{
fn add_to_all(mut self, delta: T) -> Self {
self.iter_mut().for_each(|val| *val += delta);
self
}
fn sub_from_all(mut self, sub: T) -> Self {
self.iter_mut().for_each(|val| *val -= sub);
self
}
}
impl<T> ApplyDelta<T> for Vec<(T, T)>
where
T: Number,
{
fn add_to_all(mut self, delta: T) -> Self {
self.iter_mut().for_each(|(val1, val2)| {
*val1 += delta;
*val2 += delta
});
self
}
fn sub_from_all(mut self, sub: T) -> Self {
self.iter_mut().for_each(|(val1, val2)| {
*val1 -= sub;
*val2 -= sub;
});
self
}
}
pub trait ApplyDelta2<T> {
fn add_to_all(&mut self, delta: T);
fn sub_from_all(&mut self, sub: T);
}
impl<T> ApplyDelta2<T> for [T]
where
T: Number,
T: Sized,
{
fn add_to_all(self: &mut [T], delta: T) {
self.iter_mut().for_each(|x| *x += delta);
}
fn sub_from_all(&mut self, sub: T) {
self.iter_mut().for_each(|x| *x -= sub);
}
}
}
}
pub mod seg_trees {
pub mod hld {
use std::ops::Range;
use crate::algo_lib::misc::rec_function::Callable;
use crate::algo_lib::misc::rec_function::Callable3;
use crate::algo_lib::misc::rec_function::RecursiveFunction;
use crate::algo_lib::misc::rec_function::RecursiveFunction3;
pub struct Hld {
parent: Vec<usize>,
pub order: Vec<usize>,
block_start: Vec<usize>,
pos_in_order: Vec<usize>,
}
impl Hld {
pub fn new(mut g: Vec<Vec<usize>>, tree_root: usize) -> Self {
let n = g.len();
let mut size = vec![0; n];
let mut parent = vec![0; n];
RecursiveFunction3::new(|f, v: usize, p: usize, h: usize| {
parent[v] = p;
size[v] = 1;
for &to in g[v].iter() {
if to != p {
f.call(to, v, h + 1);
size[v] += size[to];
}
}
g[v].sort_by(|&u, &v| size[u].cmp(&size[v]).reverse());
})
.call(tree_root, tree_root, 0);
let mut order = vec![];
RecursiveFunction::new(|f, v: usize| {
order.push(v);
for &to in g[v].iter() {
if to != parent[v] {
f.call(to);
}
}
})
.call(tree_root);
let mut pos_in_order = vec![0; n];
for i in 0..n {
pos_in_order[order[i]] = i;
}
let mut block_start = vec![0; n];
for i in 1..n {
if order[i - 1] == parent[order[i]] {
block_start[i] = block_start[i - 1];
} else {
block_start[i] = i;
}
}
Self {
parent,
order,
block_start,
pos_in_order,
}
}
pub fn find_path_segs(&self, mut u: usize, mut v: usize) -> Vec<Range<usize>> {
let mut segs = vec![];
while u != v {
if self.pos_in_order[u] < self.pos_in_order[v] {
std::mem::swap(&mut u, &mut v);
}
let from = std::cmp::max(
self.block_start[self.pos_in_order[u]],
self.pos_in_order[v] + 1,
);
segs.push(from..self.pos_in_order[u] + 1);
u = self.parent[self.order[from]];
}
segs.push(self.pos_in_order[v]..self.pos_in_order[v] + 1);
segs
}
pub fn lca(&self, mut v: usize, mut u: usize) -> usize {
while v != u {
if self.pos_in_order[v] < self.pos_in_order[u] {
std::mem::swap(&mut v, &mut u);
}
if self.block_start[self.pos_in_order[v]] <= self.pos_in_order[u] {
return u;
}
v = self.parent[self.order[self.block_start[self.pos_in_order[v]]]];
}
v
}
}
}
}
}
fn main() {
crate::solution::submit();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 2056kb
input:
4 1 1 2 2 1 2 2 3 2 4
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 2052kb
input:
5 1 3 2 2 1 1 2 2 3 3 4 4 5
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 2060kb
input:
6 1 1 2 2 3 3 1 2 2 3 3 4 4 5 5 6
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 2248kb
input:
6 1 2 3 4 5 6 1 2 2 3 3 4 4 5 5 6
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 2688kb
input:
2000 845 1171 345 282 1181 625 754 289 681 493 423 840 1494 318 266 1267 967 379 135 14 39 191 60 972 116 1216 1205 19 194 185 1360 861 379 430 1262 1151 756 65 389 488 277 53 1283 1438 101 1465 195 714 737 980 80 298 961 1326 163 1163 1317 1152 992 35 334 802 1502 486 710 234 555 88 1278 146 46 696...
output:
5
result:
ok single line: '5'
Test #6:
score: -100
Time Limit Exceeded
input:
200000 48015 47923 20609 71806 43752 68214 95683 89449 25809 58110 19878 52931 7845 45206 86245 82945 62977 37876 12456 105915 10509 92943 66950 88545 26442 26545 42278 66977 3970 9631 21524 43638 7979 58240 25719 56260 276 89721 9553 16550 52161 30307 82748 108443 36676 48581 59069 57412 62453 7965...