結果
| 問題 |
No.2676 A Tourist
|
| コンテスト | |
| ユーザー |
 ngtkana
|
| 提出日時 | 2024-03-04 05:03:02 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,110 bytes |
| コンパイル時間 | 12,141 ms |
| コンパイル使用メモリ | 383,160 KB |
| 実行使用メモリ | 36,864 KB |
| 最終ジャッジ日時 | 2024-09-29 23:16:01 |
| 合計ジャッジ時間 | 25,560 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 -- * 1 |
| other | AC * 5 TLE * 1 -- * 25 |
ソースコード
use input::input_array;
use input::input_vec;
use std::collections::HashSet;
fn main() {
let [n, q] = input_array::<usize, 2>();
let mut a = input_vec::<i64>();
let mut g = vec![Vec::new(); n];
for _ in 0..n - 1 {
let [u, v] = input_array::<usize, 2>();
let u = u - 1;
let v = v - 1;
g[u].push(v);
g[v].push(u);
}
let hld = hld::Hld::new(0, &g);
for _ in 0..q {
let [com, arg1, arg2] = input_array::<i64, 3>();
match com {
0 => {
let i = arg1 as usize - 1;
let x = arg2 as i64;
a[i] += x;
}
1 => {
let i = arg1 as usize - 1;
let j = arg2 as usize - 1;
let path = hld
.iter_v(i, j)
.flat_map(|(l, r)| (l..=r))
.map(|i| hld.ord()[i])
.collect::<Vec<_>>();
let mut vertices = HashSet::new();
for &x in &path {
vertices.insert(x);
for &y in &g[x] {
vertices.insert(y);
}
}
let ans = vertices.iter().map(|&x| a[x]).sum::<i64>();
println!("{}", ans);
}
_ => unreachable!(),
}
}
}
// input {{{
#[allow(dead_code)]
mod input {
use std::cell::Cell;
use std::convert::TryFrom;
use std::io::stdin;
use std::io::BufRead;
use std::io::BufReader;
use std::io::Lines;
use std::io::Stdin;
use std::str::FromStr;
use std::sync::Mutex;
use std::sync::Once;
type Server = Mutex<Lines<BufReader<Stdin>>>;
static ONCE: Once = Once::new();
pub struct Lazy(Cell<Option<Server>>);
unsafe impl Sync for Lazy {}
fn line() -> String {
static SYNCER: Lazy = Lazy(Cell::new(None));
ONCE.call_once(|| {
SYNCER
.0
.set(Some(Mutex::new(BufReader::new(stdin()).lines())));
});
unsafe {
(*SYNCER.0.as_ptr())
.as_ref()
.unwrap()
.lock()
.unwrap()
.next()
.unwrap()
.unwrap()
}
}
pub trait ForceFromStr: FromStr {
fn force_from_str(s: &str) -> Self;
}
impl<T, E> ForceFromStr for T
where
T: FromStr<Err = E>,
E: std::fmt::Debug,
{
fn force_from_str(s: &str) -> Self {
s.parse().unwrap()
}
}
pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
where
T: std::fmt::Debug,
{
<[_; N]>::try_from(input_vec()).unwrap()
}
pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
line()
.split_whitespace()
.map(T::force_from_str)
.collect::<Vec<_>>()
}
pub fn input<T: ForceFromStr>() -> T {
T::force_from_str(&line())
}
}
// }}}
// hld {{{
#[allow(dead_code)]
mod hld {
use std::mem::swap;
use std::usize::MAX;
#[derive(Clone, Debug, Default, Hash, PartialEq, Eq)]
pub struct Hld {
child: Vec<Vec<usize>>,
size: Vec<usize>,
time: Vec<usize>,
ord: Vec<usize>,
parent: Vec<usize>,
head: Vec<usize>,
}
impl Hld {
pub fn new(root: usize, g: &[Vec<usize>]) -> Self {
let (child, [size, time, ord, parent, head]) = hld(root, g);
Self {
child,
size,
time,
ord,
parent,
head,
}
}
pub fn child(&self) -> &[Vec<usize>] {
&self.child
}
pub fn size(&self) -> &[usize] {
&self.size
}
pub fn time(&self) -> &[usize] {
&self.time
}
pub fn ord(&self) -> &[usize] {
&self.ord
}
pub fn parent(&self) -> &[usize] {
&self.parent
}
pub fn head(&self) -> &[usize] {
&self.head
}
pub fn is_adjacent(&self, u: usize, v: usize) -> bool {
self.parent[u] == v || u == self.parent[v]
}
pub fn adjacent_toward(&self, x: usize, toward: usize) -> usize {
if self.is_ancestor_of(x, toward) {
self.child[x]
.iter()
.copied()
.find(|&y| self.is_ancestor_of(y, toward))
.unwrap()
} else {
self.parent[x]
}
}
pub fn dist(&self, u: usize, v: usize) -> usize {
self.iter_e(u, v).map(|(l, r)| r - l + 1).sum::<usize>()
}
pub fn lca(&self, u: usize, v: usize) -> usize {
let (u, v) = self.iter_v(u, v).last().unwrap();
self.ord[u.min(v)]
}
pub fn is_ancestor_of(&self, p: usize, u: usize) -> bool {
self.lca(p, u) == p
}
pub fn between(&self, a: usize, b: usize, c: usize) -> bool {
let mid = self.time[b];
self.iter_v(a, c)
.any(|(left, right)| (left..=right).contains(&mid))
}
pub fn iter_v(&self, u: usize, v: usize) -> IterV<'_> {
IterV {
hld: self,
u,
v,
finish: false,
}
}
pub fn iter_e(&self, u: usize, v: usize) -> IterE<'_> {
IterE {
hld: self,
u,
v,
finish: false,
}
}
}
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct IterV<'a> {
hld: &'a Hld,
u: usize,
v: usize,
finish: bool,
}
impl Iterator for IterV<'_> {
type Item = (usize, usize);
fn next(&mut self) -> Option<Self::Item> {
if self.finish {
return None;
}
let Self { hld, u, v, .. } = self;
if hld.time[*u] > hld.time[*v] {
swap(u, v);
}
Some(if hld.head[*u] == hld.head[*v] {
self.finish = true;
(hld.time[*u], hld.time[*v])
} else {
let h = hld.head[*v];
let ans = (hld.time[h], hld.time[*v]);
*v = hld.parent[h];
ans
})
}
}
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct IterE<'a> {
hld: &'a Hld,
u: usize,
v: usize,
finish: bool,
}
impl Iterator for IterE<'_> {
type Item = (usize, usize);
fn next(&mut self) -> Option<Self::Item> {
if self.finish {
return None;
}
let Self { hld, u, v, .. } = self;
if hld.time[*u] > hld.time[*v] {
swap(u, v);
}
if hld.head[*u] == hld.head[*v] {
self.finish = true;
if *u == *v {
None
} else {
Some((hld.time[*u] + 1, hld.time[*v]))
}
} else {
let h = hld.head[*v];
let ans = (hld.time[h], hld.time[*v]);
*v = hld.parent[h];
Some(ans)
}
}
}
fn hld(root: usize, g: &[Vec<usize>]) -> (Vec<Vec<usize>>, [Vec<usize>; 5]) {
let n = g.len();
let mut size = vec![1; n];
let mut child = vec![Vec::<usize>::new(); n];
dfs(root, root, g, &mut size, &mut child);
let mut ord = Vec::new();
let mut time = vec![MAX; n];
let mut parent = vec![MAX; n];
let mut head = vec![MAX; n];
parent[root] = root;
head[root] = root;
efs(root, &child, &mut time, &mut ord, &mut parent, &mut head);
(child, [size, time, ord, parent, head])
}
fn dfs(x: usize, p: usize, g: &[Vec<usize>], size: &mut [usize], child: &mut [Vec<usize>]) {
let mut gx = g[x].iter().copied().filter(|&y| y != p).collect::<Vec<_>>();
if !gx.is_empty() {
for &y in &gx {
dfs(y, x, g, size, child);
size[x] += size[y];
}
let max_position = (0..gx.len()).max_by_key(|&i| size[gx[i]]).unwrap();
gx.swap(0, max_position);
}
child[x] = gx;
}
fn efs(
x: usize,
g: &[Vec<usize>],
time: &mut [usize],
ord: &mut Vec<usize>,
parent: &mut [usize],
head: &mut [usize],
) {
time[x] = ord.len();
ord.push(x);
if !g[x].is_empty() {
let h = g[x][0];
head[h] = head[x];
parent[h] = x;
efs(h, g, time, ord, parent, head);
for &y in &g[x][1..] {
head[y] = y;
parent[y] = x;
efs(y, g, time, ord, parent, head);
}
}
}
}
// }}}