結果
| 問題 | No.1600 Many Shortest Path Problems |
| ユーザー |
 ngtkana
|
| 提出日時 | 2021-05-08 11:29:54 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 971 ms / 4,000 ms |
| コード長 | 57,881 bytes |
| コンパイル時間 | 15,230 ms |
| コンパイル使用メモリ | 379,204 KB |
| 実行使用メモリ | 55,424 KB |
| 最終ジャッジ日時 | 2024-07-01 14:20:35 |
| 合計ジャッジ時間 | 39,971 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 1 ms
5,376 KB |
| testcase_04 | AC | 961 ms
53,132 KB |
| testcase_05 | AC | 971 ms
53,000 KB |
| testcase_06 | AC | 1 ms
5,376 KB |
| testcase_07 | AC | 1 ms
5,376 KB |
| testcase_08 | AC | 1 ms
5,376 KB |
| testcase_09 | AC | 1 ms
5,376 KB |
| testcase_10 | AC | 508 ms
29,128 KB |
| testcase_11 | AC | 584 ms
29,892 KB |
| testcase_12 | AC | 754 ms
37,468 KB |
| testcase_13 | AC | 950 ms
47,636 KB |
| testcase_14 | AC | 920 ms
53,524 KB |
| testcase_15 | AC | 1 ms
5,376 KB |
| testcase_16 | AC | 1 ms
5,376 KB |
| testcase_17 | AC | 830 ms
41,052 KB |
| testcase_18 | AC | 951 ms
53,160 KB |
| testcase_19 | AC | 1 ms
5,376 KB |
| testcase_20 | AC | 1 ms
5,376 KB |
| testcase_21 | AC | 842 ms
41,180 KB |
| testcase_22 | AC | 1 ms
5,376 KB |
| testcase_23 | AC | 1 ms
5,376 KB |
| testcase_24 | AC | 935 ms
53,276 KB |
| testcase_25 | AC | 1 ms
5,376 KB |
| testcase_26 | AC | 1 ms
5,376 KB |
| testcase_27 | AC | 1 ms
5,376 KB |
| testcase_28 | AC | 1 ms
5,376 KB |
| testcase_29 | AC | 596 ms
55,420 KB |
| testcase_30 | AC | 636 ms
52,736 KB |
| testcase_31 | AC | 812 ms
41,148 KB |
| testcase_32 | AC | 800 ms
41,168 KB |
| testcase_33 | AC | 1 ms
5,376 KB |
| testcase_34 | AC | 1 ms
5,376 KB |
| testcase_35 | AC | 789 ms
52,780 KB |
| testcase_36 | AC | 587 ms
48,120 KB |
| testcase_37 | AC | 1 ms
5,376 KB |
| testcase_38 | AC | 617 ms
52,860 KB |
| testcase_39 | AC | 1 ms
5,376 KB |
| testcase_40 | AC | 640 ms
52,604 KB |
| testcase_41 | AC | 557 ms
55,424 KB |
| testcase_42 | AC | 579 ms
52,776 KB |
| testcase_43 | AC | 583 ms
52,864 KB |
| testcase_44 | AC | 609 ms
49,172 KB |
| testcase_45 | AC | 600 ms
55,420 KB |
| testcase_46 | AC | 616 ms
52,736 KB |
| testcase_47 | AC | 643 ms
52,864 KB |
| testcase_48 | AC | 645 ms
52,124 KB |
| testcase_49 | AC | 1 ms
5,376 KB |
| testcase_50 | AC | 1 ms
5,376 KB |
| testcase_51 | AC | 1 ms
5,376 KB |
| testcase_52 | AC | 1 ms
5,376 KB |
| testcase_53 | AC | 1 ms
5,376 KB |
コンパイルメッセージ
warning: unused imports: `Table`, `bitslice::BitSlice`, `table`
--> src/main.rs:664:13
|
664 | bitslice::BitSlice,
| ^^^^^^^^^^^^^^^^^^
665 | table::{table, Table},
| ^^^^^ ^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused imports: `Leaf`, `Tuple`, `VecLen`
--> src/main.rs:1545:27
|
1545 | multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen},
| ^^^^ ^^^^^ ^^^^^^
warning: unused import: `with_str`
--> src/main.rs:1801:35
|
1801 | pub use self::i::{with_stdin, with_str};
| ^^^^^^^^
warning: unused imports: `ParserTuple`, `Parser`, `RawTuple`, `Token`, `Usize1`
--> src/main.rs:1804:28
|
1804 | pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1};
| ^^^^^^ ^^^^^^^^^^^ ^^^^^^^^ ^^^^^ ^^^^^^
ソースコード
use crate::{segtree::Segtree, uf_checklist::UfChecklist};
use fp::F1000000007 as Fp;
use hld::Hld;
use ngtio::with_stdin;
use std::{collections::HashMap, iter::repeat_with, mem::swap, ops::Add};
use union_find::UnionFind;
fn main() {
let mut buf = with_stdin();
let n = buf.usize();
let m = buf.usize();
let edges = repeat_with(|| [buf.usize() - 1, buf.usize() - 1])
.take(m)
.collect::<Vec<_>>();
let q = buf.usize();
let queries = repeat_with(|| ([buf.usize() - 1, buf.usize() - 1], buf.usize() - 1))
.take(q)
.collect::<Vec<_>>();
let ans = solve(n, &edges, &queries);
for ans in &ans {
if let Some(ans) = ans {
println!("{}", ans);
} else {
println!("-1");
}
}
}
fn solve(n: usize, edges: &[[usize; 2]], queries: &[([usize; 2], usize)]) -> Vec<Option<Fp>> {
let m = edges.len();
// MST を構築して、辺をストックです。
let mut uf = UnionFind::new(n);
let mut mst = vec![Vec::new(); n];
let mut map = HashMap::new();
let mut in_mst = vec![false; m];
for (i, &[u, v]) in edges.iter().enumerate() {
if !uf.same(u, v) {
uf.union(u, v);
mst[u].push(v);
mst[v].push(u);
in_mst[i] = true;
}
map.insert([u, v], i);
map.insert([v, u], i);
}
// 回避予行演習です。
let mut ufc = UfChecklist::new(m);
let hld = Hld::new(0, &mut mst);
let mut forb_e_to_avoid_e = vec![None; m];
for (avoid_e, &[u, v]) in edges.iter().enumerate().filter(|&(i, _)| !in_mst[i]) {
for (l, r) in hld.iter_e(u, v) {
for forb_e in ufc.range_check(l..=r).map(|i| {
let x = hld.ord()[i];
let p = hld.parent()[x];
assert_ne!(x, p);
map[&[p, x]]
}) {
if forb_e_to_avoid_e[forb_e].is_none() {
forb_e_to_avoid_e[forb_e] = Some(avoid_e);
}
}
}
}
// 辺の重みをセグツリーに載せておきます。
let seg_time_to_weight = Segtree::new(
&hld.ord()
.iter()
.map(|&i| {
let p = hld.parent()[i];
if i == p {
Fp::new(0)
} else {
Fp::new(2).pow(map[&[p, i]] as u32 + 1)
}
})
.collect::<Vec<_>>(),
Add::add,
|| Fp::new(0),
);
// クエリ処理パートです。
queries
.iter()
.map(|&([end_v0, end_v1], forb_e)| {
let [mut forb_v0, mut forb_v1] = edges[forb_e];
if hld.time()[forb_v0] > hld.time()[forb_v1] {
swap(&mut forb_v0, &mut forb_v1);
}
if in_mst[forb_e]
&& hld.between(end_v0, forb_v0, end_v1)
&& hld.between(end_v0, forb_v1, end_v1)
{
// 回避が必要な場合
forb_e_to_avoid_e[forb_e].map(|avoid_e| {
let avoid_cost = Fp::new(2).pow(avoid_e as u32 + 1);
let [avoid_v0, avoid_v1] = edges[avoid_e];
if hld.dist(end_v0, avoid_v0) + hld.dist(avoid_v1, end_v1)
< hld.dist(end_v0, avoid_v1) + hld.dist(avoid_v0, end_v1)
{
hld.iter_e(end_v0, avoid_v0)
.map(|(l, r)| seg_time_to_weight.fold(l..=r))
.sum::<Fp>()
+ avoid_cost
+ hld
.iter_e(avoid_v1, end_v1)
.map(|(l, r)| seg_time_to_weight.fold(l..=r))
.sum::<Fp>()
} else {
hld.iter_e(end_v0, avoid_v1)
.map(|(l, r)| seg_time_to_weight.fold(l..=r))
.sum::<Fp>()
+ avoid_cost
+ hld
.iter_e(avoid_v0, end_v1)
.map(|(l, r)| seg_time_to_weight.fold(l..=r))
.sum::<Fp>()
}
})
} else {
// 回避不要な場合
Some(
hld.iter_e(end_v0, end_v1)
.map(|(l, r)| seg_time_to_weight.fold(l..=r))
.sum::<Fp>(),
)
}
})
.collect::<Vec<_>>()
}
#[cfg(test)]
mod tests {
use super::{solve, union_find::UnionFind, Fp};
use make_graph::array_make_undirected_weighted;
use rand::{
prelude::{SliceRandom, StdRng},
Rng, SeedableRng,
};
use std::{
cmp::Reverse,
collections::{BinaryHeap, HashSet},
iter::repeat_with,
mem::swap,
u64::MAX,
};
#[test]
fn test_solve() {
let mut rng = StdRng::seed_from_u64(42);
for _ in 0..500 {
let n = rng.gen_range(2, 15);
let m = rng.gen_range(n - 1, (n * (n - 1) / 2 + 1).min(15));
let edges = gen_connected_graph(&mut rng, n, m);
let q = n;
let queries = repeat_with(|| {
let [u, v] = gen_strictly_increasing_pair(&mut rng, n);
let i = rng.gen_range(0, m);
([u, v], i)
})
.take(q)
.collect::<Vec<_>>();
println!("n = {}, edges = {:?}, queries = {:?}", n, &edges, &queries);
let result = solve(n, &edges, &queries);
let expected = brute(n, &edges, &queries);
assert_eq!(result, expected);
}
}
fn gen_connected_graph(rng: &mut StdRng, n: usize, m: usize) -> Vec<[usize; 2]> {
let mut uf = UnionFind::new(n);
let mut edges = HashSet::new();
for _ in 0..n - 1 {
loop {
let [u, v] = gen_strictly_increasing_pair(rng, n);
if !uf.same(u, v) {
uf.union(u, v);
edges.insert([u, v]);
break;
}
}
}
for _ in 0..m - (n - 1) {
loop {
let [u, v] = gen_strictly_increasing_pair(rng, n);
if !edges.contains(&[u, v]) {
edges.insert([u, v]);
break;
}
}
}
let mut edges = edges.into_iter().collect::<Vec<_>>();
edges.shuffle(rng);
edges
}
fn gen_strictly_increasing_pair(rng: &mut StdRng, n: usize) -> [usize; 2] {
let mut u = rng.gen_range(0, n - 1);
let mut v = rng.gen_range(0, n);
if u >= v {
swap(&mut u, &mut v);
v += 1;
}
assert!(u < v);
[u, v]
}
fn brute(n: usize, edges: &[[usize; 2]], queries: &[([usize; 2], usize)]) -> Vec<Option<Fp>> {
let edges = edges
.into_iter()
.enumerate()
.map(|(i, &[u, v])| ([u, v], 2u64.pow(i as u32 + 1)))
.collect::<Vec<_>>();
let mut g = array_make_undirected_weighted(n, edges.as_slice());
queries
.iter()
.map(|&([u, v], e)| {
let ([e0, e1], w) = edges[e];
remove_item(&mut g[e0], &(e1, w));
remove_item(&mut g[e1], &(e0, w));
let mut dist = vec![MAX; n];
dist[u] = 0;
let mut heap = BinaryHeap::from(vec![(Reverse(0), u)]);
while let Some((Reverse(dx), x)) = heap.pop() {
if dist[x] < dx {
continue;
}
for &(y, w) in &g[x] {
let dy = dx + w;
if dy < dist[y] {
heap.push((Reverse(dy), y));
dist[y] = dy;
}
}
}
g[e0].push((e1, w));
g[e1].push((e0, w));
if dist[v] == MAX {
None
} else {
Some(Fp::from(dist[v]))
}
})
.collect::<Vec<_>>()
}
fn remove_item<T, V>(me: &mut Vec<T>, item: &V) -> Option<T>
where
T: PartialEq<V>,
{
let pos = me.iter().position(|x| *x == *item)?;
Some(me.remove(pos))
}
// bfs {{{
#[allow(dead_code)]
mod bfs {
use std::collections::VecDeque;
pub fn tree_diamter(g: &[Vec<usize>]) -> ([usize; 2], u32) {
assert_eq!(g.iter().flatten().count(), (g.len() - 1) * 2);
let dist = calc_dist(0, g);
let &diam = dist.iter().max().unwrap();
let x = dist.iter().position(|&d| d == diam).unwrap();
let dist = calc_dist(x, g);
let &diam = dist.iter().max().unwrap();
let y = dist.iter().position(|&d| d == diam).unwrap();
([x, y], diam)
}
pub fn tree_diamter_restore(g: &[Vec<usize>]) -> (Vec<usize>, u32) {
assert_eq!(g.iter().flatten().count(), (g.len() - 1) * 2);
let dist = calc_dist(0, g);
let &diam = dist.iter().max().unwrap();
let x = dist.iter().position(|&d| d == diam).unwrap();
let (dist, prv) = calc_dist_restore(x, g);
let &diam = dist.iter().max().unwrap();
let mut res = vec![dist.iter().position(|&d| d == diam).unwrap()];
loop {
let x = *res.last().unwrap();
if dist[x] == 0 {
break;
}
res.push(prv[x]);
}
(res, diam)
}
pub fn calc_dist(start: usize, g: &[Vec<usize>]) -> Vec<u32> {
let mut dist = vec![std::u32::MAX; g.len()];
dist[start] = 0;
let mut queue = VecDeque::from(vec![start]);
while let Some(x) = queue.pop_front() {
for &y in &g[x] {
if dist[y] == std::u32::MAX {
dist[y] = dist[x] + 1;
queue.push_back(y);
}
}
}
dist
}
pub fn calc_dist_restore(start: usize, g: &[Vec<usize>]) -> (Vec<u32>, Vec<usize>) {
let mut dist = vec![std::u32::MAX; g.len()];
let mut prv = vec![std::usize::MAX; g.len()];
dist[start] = 0;
prv[start] = start;
let mut queue = VecDeque::from(vec![start]);
while let Some(x) = queue.pop_front() {
for &y in &g[x] {
if dist[y] == std::u32::MAX {
dist[y] = dist[x] + 1;
prv[y] = x;
queue.push_back(y);
}
}
}
(dist, prv)
}
pub fn find_path(start: usize, end: usize, g: &[Vec<usize>]) -> Option<Vec<usize>> {
let (dist, prv) = calc_dist_restore(start, g);
if dist[end] == std::u32::MAX {
None
} else {
let mut res = vec![end];
loop {
let x = *res.last().unwrap();
if x == start {
res.reverse();
return Some(res);
}
res.push(prv[x]);
}
}
}
}
// }}}
// make_graph {{{
#[allow(dead_code)]
mod make_graph {
pub fn tuple_make_undirected(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
make_undirected_by(n, edges, |&(u, v)| [u, v])
}
pub fn array_make_undirected(n: usize, edges: &[[usize; 2]]) -> Vec<Vec<usize>> {
make_undirected_by(n, edges, |&[u, v]| [u, v])
}
pub fn make_undirected_by<E>(
n: usize,
edges: &[E],
f: impl Fn(&E) -> [usize; 2],
) -> Vec<Vec<usize>> {
let mut g = vec![Vec::new(); n];
for [u, v] in edges.iter().map(f) {
g[u].push(v);
g[v].push(u);
}
g
}
pub fn tuple_make_directed(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
make_directed_by(n, edges, |&(u, v)| [u, v])
}
pub fn array_make_directed(n: usize, edges: &[[usize; 2]]) -> Vec<Vec<usize>> {
make_directed_by(n, edges, |&[u, v]| [u, v])
}
pub fn make_directed_by<E>(
n: usize,
edges: &[E],
f: impl Fn(&E) -> [usize; 2],
) -> Vec<Vec<usize>> {
let mut g = vec![Vec::new(); n];
edges.iter().map(f).for_each(|[u, v]| g[u].push(v));
g
}
pub fn tuple_make_undirected_weighted<T: Copy>(
n: usize,
edges: &[(usize, usize, T)],
) -> Vec<Vec<(usize, T)>> {
make_undirected_weighted_by(n, edges, |&(u, v, x)| ([u, v], x))
}
pub fn array_make_undirected_weighted<T: Copy>(
n: usize,
edges: &[([usize; 2], T)],
) -> Vec<Vec<(usize, T)>> {
make_undirected_weighted_by(n, edges, |&([u, v], x)| ([u, v], x))
}
pub fn make_undirected_weighted_by<E, T: Copy>(
n: usize,
edges: &[E],
f: impl Fn(&E) -> ([usize; 2], T),
) -> Vec<Vec<(usize, T)>> {
let mut g = vec![Vec::new(); n];
for ([u, v], x) in edges.iter().map(f) {
g[u].push((v, x));
g[v].push((u, x));
}
g
}
pub fn tuple_make_directed_weighted<T: Copy>(
n: usize,
edges: &[(usize, usize, T)],
) -> Vec<Vec<(usize, T)>> {
make_directed_weighted_by(n, edges, |&(u, v, x)| ([u, v], x))
}
pub fn array_make_directed_weighted<T: Copy>(
n: usize,
edges: &[([usize; 2], T)],
) -> Vec<Vec<(usize, T)>> {
make_directed_weighted_by(n, edges, |&([u, v], x)| ([u, v], x))
}
pub fn make_directed_weighted_by<E, T: Copy>(
n: usize,
edges: &[E],
f: impl Fn(&E) -> ([usize; 2], T),
) -> Vec<Vec<(usize, T)>> {
let mut g = vec![Vec::new(); n];
edges
.iter()
.map(f)
.for_each(|([u, v], w)| g[u].push((v, w)));
g
}
}
// }}}
}
// uf_checklist {{{
#[allow(dead_code)]
mod uf_checklist {
use {
crate::union_find::UnionFind,
std::ops::{Bound, Range, RangeBounds},
};
#[derive(Clone, Debug)]
pub struct UfChecklist {
uf: UnionFind,
rightmost: Vec<usize>,
}
impl UfChecklist {
pub fn new(n: usize) -> Self {
Self {
uf: UnionFind::new(n + 1),
rightmost: (0..=n).collect::<Vec<_>>(),
}
}
pub fn range_check(&mut self, range: impl RangeBounds<usize>) -> Iter<'_> {
let n = self.rightmost.len() - 1;
let Range { mut start, end } = open(range, n);
assert!(
start <= end && end <= n,
"範囲外です。start = {}, end = {}, n = {}",
start,
end,
n
);
start = __next_unckecked_cell(self, start);
Iter {
range_check: self,
start,
end,
}
}
pub fn lower_bound(&self, i: usize) -> Option<usize> {
let n = self.rightmost.len() - 1;
assert!(i < n, "範囲外です。 i = {}, n = {}", i, n);
let i = __next_unckecked_cell(self, i);
if i == self.rightmost.len() - 1 {
None
} else {
Some(i)
}
}
pub fn is_checked(&self, i: usize) -> bool {
let n = self.rightmost.len() - 1;
assert!(i < n, "範囲外です。 i = {}, n = {}", i, n);
self.rightmost[self.uf.find(i)] != i
}
pub fn check(&mut self, i: usize) -> bool {
let n = self.rightmost.len() - 1;
assert!(i < n, "範囲外です。 i = {}, n = {}", i, n);
if self.rightmost[self.uf.find(i)] == i {
let next = __next_unckecked_cell(self, i + 1);
self.uf.union(i, next);
self.rightmost[self.uf.find(next)] = next;
true
} else {
false
}
}
}
fn __next_unckecked_cell(range_check: &UfChecklist, i: usize) -> usize {
range_check.rightmost[range_check.uf.find(i)]
}
#[derive(Debug)]
pub struct Iter<'a> {
range_check: &'a mut UfChecklist,
start: usize,
end: usize,
}
impl Iterator for Iter<'_> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
let Self {
range_check,
start,
end,
} = self;
if *start < *end {
let ans = *start;
let check_result = range_check.check(*start);
assert!(check_result);
let next = __next_unckecked_cell(&range_check, *start);
*start = next;
Some(ans)
} else {
None
}
}
}
fn open(range: impl RangeBounds<usize>, len: usize) -> Range<usize> {
(match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(&x) => x,
Bound::Excluded(&x) => x + 1,
})..match range.end_bound() {
Bound::Excluded(&x) => x,
Bound::Included(&x) => x + 1,
Bound::Unbounded => len,
}
}
// dbg {{{
#[allow(dead_code)]
mod dbg {
mod bitslice {
use std::fmt::{self, Debug, Display, Formatter};
pub struct BitSlice<'a>(pub &'a [bool]);
impl<'a> Display for BitSlice<'a> {
fn fmt(&self, w: &mut Formatter) -> fmt::Result {
write!(
w,
"{}",
self.0
.iter()
.map(|&b| if b { '1' } else { '0' })
.collect::<String>()
)
}
}
impl<'a> Debug for BitSlice<'a> {
fn fmt(&self, w: &mut Formatter) -> fmt::Result {
write!(w, "{}", self)
}
}
}
mod table {
use std::{
fmt::{self, Debug, Formatter},
marker::PhantomData,
};
pub fn table<T, U>(table: &[U]) -> Table<'_, T, U> {
Table {
_marker: PhantomData,
table,
}
}
pub struct Table<'a, T, U> {
table: &'a [U],
_marker: PhantomData<T>,
}
impl<'a, T, U> Clone for Table<'a, T, U> {
fn clone(&self) -> Self {
Self {
table: self.table,
_marker: PhantomData,
}
}
}
impl<'a, T, U> Copy for Table<'a, T, U> {}
impl<'a, T, U> Debug for Table<'a, T, U>
where
T: Debug,
U: AsRef<[T]>,
{
fn fmt(&self, w: &mut Formatter) -> fmt::Result {
write!(w, "{:?}", self.by(|cell| format!("{:?}", cell)))
}
}
impl<'a, T, U> Table<'a, T, U> {
pub fn by<F>(self, f: F) -> TableF<'a, T, U, F>
where
T: Debug,
U: AsRef<[T]>,
F: Fn(&T) -> String,
{
TableF {
_marker: PhantomData,
table: self.table,
f,
}
}
}
pub struct TableF<'a, T, U, F> {
pub _marker: PhantomData<T>,
pub table: &'a [U],
pub f: F,
}
impl<'a, T, U, F: Clone> Clone for TableF<'a, T, U, F> {
fn clone(&self) -> Self {
Self {
table: self.table,
_marker: PhantomData,
f: self.f.clone(),
}
}
}
impl<'a, T, U, F: Copy> Copy for TableF<'a, T, U, F> {}
impl<'a, T, U, F> Debug for TableF<'a, T, U, F>
where
T: Debug,
U: AsRef<[T]>,
F: Fn(&T) -> String,
{
fn fmt(&self, w: &mut Formatter) -> fmt::Result {
self.table
.iter()
.enumerate()
.try_for_each(|(row_index, row)| {
writeln!(
w,
"{:02}|{}",
row_index,
row.as_ref()
.iter()
.map(|cell| format!(" {}", (&self.f)(cell)))
.collect::<String>()
)
})
}
}
}
pub use {
bitslice::BitSlice,
table::{table, Table},
};
#[macro_export]
macro_rules! lg {
(@nl $value:expr) => {
eprintln!("[{}:{}]", file!(), line!());
match $value {
value => {
eprint!("{:?}", &value);
}
}
};
(@contents $head:expr $(,)?) => {
match $head {
head => {
eprintln!(" {} = {:?}", stringify!($head), &head);
}
}
};
(@contents $head:expr $(,$tail:expr)+ $(,)?) => {
match $head {
head => {
eprint!(" {} = {:?},", stringify!($head), &head);
}
}
$crate::lg!(@contents $($tail),*);
};
($($expr:expr),* $(,)?) => {
eprint!("[{}:{}]", file!(), line!());
$crate::lg!(@contents $($expr),*)
};
}
}
// }}}
}
// }}}
// hld {{{
#[allow(dead_code)]
mod hld {
use std::{mem::swap, usize::MAX};
#[derive(Clone, Debug, Default, Hash, PartialEq)]
pub struct Hld {
time: Vec<usize>,
ord: Vec<usize>,
parent: Vec<usize>,
head: Vec<usize>,
}
impl Hld {
pub fn new(root: usize, g: &mut [Vec<usize>]) -> Self {
let (time, ord, parent, head) = hld(root, g);
Self {
time,
ord,
parent,
head,
}
}
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 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 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, Copy)]
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] {
let h = hld.head[*v];
let ans = (hld.time[h], hld.time[*v]);
assert_ne!(hld.parent[h], h, "入力のグラフが非連結です。");
*v = hld.parent[h];
ans
} else {
self.finish = true;
(hld.time[*u], hld.time[*v])
})
}
}
#[derive(Clone, Debug, Hash, PartialEq, Copy)]
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] {
let h = hld.head[*v];
let ans = (hld.time[h], hld.time[*v]);
assert_ne!(hld.parent[h], h, "入力のグラフが非連結です。");
*v = hld.parent[h];
Some(ans)
} else {
self.finish = true;
if *u == *v {
None
} else {
Some((hld.time[*u] + 1, hld.time[*v]))
}
}
}
}
fn hld(root: usize, g: &mut [Vec<usize>]) -> (Vec<usize>, Vec<usize>, Vec<usize>, Vec<usize>) {
dfs(root, root, g);
let mut ord = Vec::new();
let mut time = vec![MAX; g.len()];
let mut parent = vec![MAX; g.len()];
let mut head = vec![MAX; g.len()];
parent[root] = root;
head[root] = root;
efs(root, &g, &mut time, &mut ord, &mut parent, &mut head);
assert!(parent.iter().all(|&x| x != MAX), "入力が非連結です。");
(time, ord, parent, head)
}
fn dfs(x: usize, p: usize, g: &mut [Vec<usize>]) -> usize {
let mut child = g[x].iter().copied().filter(|&y| y != p).collect::<Vec<_>>();
let mut size = 1;
let mut max_size = 1;
for i in 0..child.len() {
let s = dfs(child[i], x, g);
if max_size < s {
max_size = s;
child.swap(0, i);
}
size += s;
}
g[x] = child;
size
}
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);
}
}
}
}
// }}}
// fp {{{
#[allow(dead_code)]
mod fp {
use std::{
cmp::PartialEq,
fmt,
hash::{Hash, Hasher},
iter::{successors, Product, Sum},
marker::PhantomData,
mem::swap,
ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};
pub trait Mod: Clone + Copy + Hash {
const P: u32;
const K: u32;
const R2: u32 = ((1_u128 << 64) % Self::P as u128) as _; // 2 ^ 64 mod P
}
fn reduce<M: Mod>(x: u64) -> u32 {
((x + u64::from(M::K.wrapping_mul(x as u32)) * u64::from(M::P)) >> 32) as u32
}
pub fn fact_iter<M: Mod>() -> impl Iterator<Item = Fp<M>> {
(1..).scan(Fp::new(1), |state, x| {
let ans = *state;
*state *= x;
Some(ans)
})
}
#[allow(clippy::missing_panics_doc)]
pub fn fact_build<M: Mod>(n: usize) -> [Vec<Fp<M>>; 2] {
if n == 0 {
[Vec::new(), Vec::new()]
} else {
let fact = fact_iter::<M>().take(n).collect::<Vec<_>>();
let mut fact_inv = vec![fact.last().unwrap().recip(); n];
(1..n).rev().for_each(|i| fact_inv[i - 1] = fact_inv[i] * i);
[fact, fact_inv]
}
}
pub fn binom_iter<M: Mod>() -> impl Iterator<Item = Vec<Fp<M>>> {
successors(Some(vec![Fp::new(1)]), |last| {
let mut crr = last.clone();
crr.push(Fp::new(0));
crr[1..].iter_mut().zip(last).for_each(|(x, &y)| *x += y);
Some(crr)
})
}
#[macro_export]
macro_rules! define_mod {
($(($Fp: ident, $Mod: ident, $mod: expr, $k: expr),)*) => {$(
#[derive(Clone, Debug, Default, Hash, Copy)]
pub struct $Mod {}
impl Mod for $Mod {
const P: u32 = $mod;
const K: u32 = $k;
}
pub type $Fp = Fp<$Mod>;
)*}
}
define_mod! {
(F998244353, Mod998244353, 998_244_353, 998_244_351),
(F1000000007, Mod1000000007, 1_000_000_007, 2_226_617_417),
(F1012924417, Mod1012924417, 1_012_924_417, 1_012_924_415),
(F924844033, Mod924844033, 924_844_033, 924_844_031),
}
#[derive(Clone, Default, Copy)]
pub struct Fp<M> {
value: u32,
__marker: PhantomData<M>,
}
impl<M: Mod> Fp<M> {
pub const P: u32 = M::P;
pub fn new(value: u32) -> Self {
Self::from_raw(reduce::<M>(u64::from(value) * u64::from(M::R2)))
}
pub fn value(self) -> u32 {
let x = reduce::<M>(u64::from(self.value));
if M::P <= x {
x - M::P
} else {
x
}
}
#[allow(clippy::many_single_char_names)]
pub fn recip(self) -> Self {
assert_ne!(self, Self::new(0), "0 はだめ。");
let mut x = M::P as i32;
let mut y = self.value() as i32;
let mut u = 0;
let mut v = 1;
while y != 0 {
let q = x / y;
x -= q * y;
u -= q * v;
swap(&mut x, &mut y);
swap(&mut u, &mut v);
}
debug_assert_eq!(x, 1);
if u < 0 {
debug_assert_eq!(v, M::P as i32);
u += v;
}
Self::new(u as u32)
}
pub fn pow<T: Into<u64>>(self, exp: T) -> Self {
let mut exp = exp.into();
if exp == 0 {
return Self::new(1);
}
let mut base = self;
let mut acc = Self::new(1);
while 1 < exp {
if exp & 1 == 1 {
acc *= base;
}
exp /= 2;
base *= base;
}
acc * base
}
fn from_raw(value: u32) -> Self {
Self {
value,
__marker: PhantomData,
}
}
}
fn simplify(value: i32, p: i32) -> (i32, i32, i32) {
if value.abs() < 10_000 {
(value, 1, 0)
} else {
let mut q = p.div_euclid(value);
let mut r = p.rem_euclid(value);
if value <= 2 * r {
q += 1;
r -= value;
}
let (num, pden, ppden) = simplify(r, value);
let den = ppden - q * pden;
(num, den, pden)
}
}
macro_rules! impl_from_large_int {
($($T: ty), *$(,)?) => {$(
impl<M: Mod> From<$T> for Fp<M> {
fn from(x: $T) -> Self {
Self::new(x.rem_euclid(M::P as _) as u32)
}
}
)*}
}
impl_from_large_int! {
u32, u64, u128, usize,
i32, i64, i128, isize,
}
macro_rules! impl_from_small_int {
($($T: ty), *$(,)?) => {$(
impl<M: Mod> From<$T> for Fp<M> {
fn from(x: $T) -> Self {
Self::new(x as u32)
}
}
)*}
}
impl_from_small_int! {
u8, u16,
i8, i16,
}
impl<M: Mod> PartialEq for Fp<M> {
fn eq(&self, other: &Self) -> bool {
fn value<M: Mod>(fp: Fp<M>) -> u32 {
if fp.value >= M::P {
fp.value - M::P
} else {
fp.value
}
}
value(*self) == value(*other)
}
}
impl<M: Mod> Eq for Fp<M> {}
impl<M: Mod> Hash for Fp<M> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.value().hash(state);
}
}
impl<M: Mod, T: Into<Self>> AddAssign<T> for Fp<M> {
fn add_assign(&mut self, rhs: T) {
self.value += rhs.into().value;
if M::P * 2 <= self.value {
self.value -= M::P * 2;
}
}
}
impl<M: Mod, T: Into<Self>> SubAssign<T> for Fp<M> {
fn sub_assign(&mut self, rhs: T) {
let rhs = rhs.into();
if self.value < rhs.value {
self.value += M::P * 2;
}
self.value -= rhs.value;
}
}
impl<M: Mod, T: Into<Self>> MulAssign<T> for Fp<M> {
fn mul_assign(&mut self, rhs: T) {
self.value = reduce::<M>(u64::from(self.value) * u64::from(rhs.into().value));
}
}
#[allow(clippy::suspicious_op_assign_impl)]
impl<M: Mod, T: Into<Self>> DivAssign<T> for Fp<M> {
fn div_assign(&mut self, rhs: T) {
*self *= rhs.into().recip();
}
}
impl<'a, M: Mod> From<&'a Self> for Fp<M> {
fn from(x: &Self) -> Self {
*x
}
}
macro_rules! forward_ops {
($(($trait:ident, $method_assign:ident, $method:ident),)*) => {$(
impl<M: Mod, T: Into<Fp<M>>> $trait<T> for Fp<M> {
type Output = Self;
fn $method(mut self, rhs: T) -> Self {
self.$method_assign(rhs);
self
}
}
impl<'a, M: Mod, T: Into<Fp<M>>> $trait<T> for &'a Fp<M> {
type Output = Fp<M>;
fn $method(self, other: T) -> Self::Output {
$trait::$method(*self, other)
}
}
)*};
}
forward_ops! {
(Add, add_assign, add),
(Sub, sub_assign, sub),
(Mul, mul_assign, mul),
(Div, div_assign, div),
}
impl<M: Mod> Neg for Fp<M> {
type Output = Self;
fn neg(self) -> Self {
Self::from_raw(M::P * 2 - self.value)
}
}
impl<M: Mod> Sum for Fp<M> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::new(0), |b, x| b + x)
}
}
impl<M: Mod> Product for Fp<M> {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::new(1), |b, x| b * x)
}
}
impl<'a, M: Mod> Sum<&'a Self> for Fp<M> {
fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
iter.fold(Self::new(0), |b, x| b + x)
}
}
impl<'a, M: Mod> Product<&'a Self> for Fp<M> {
fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
iter.fold(Self::new(1), |b, x| b * x)
}
}
impl<M: Mod> fmt::Debug for Fp<M> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
let (num, den, _) = simplify(self.value() as i32, M::P as i32);
let (num, den) = match den.signum() {
1 => (num, den),
-1 => (-num, -den),
_ => unreachable!(),
};
if den == 1 {
write!(f, "{}", num)
} else {
write!(f, "{}/{}", num, den)
}
}
}
impl<M: Mod> fmt::Display for Fp<M> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.value().fmt(f)
}
}
}
// }}}
// segtree {{{
#[allow(dead_code)]
mod segtree {
use std::{
fmt::{self, Debug, Formatter},
ops::{Bound, Deref, DerefMut, Drop, Index, Range, RangeBounds},
slice::SliceIndex,
};
pub struct Segtree<T, Op, Ideneity> {
len: usize,
table: Box<[T]>,
op: Op,
identity: Ideneity,
}
impl<T, Op, Identity> Segtree<T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
pub fn new(slice: &[T], op: Op, identity: Identity) -> Self {
let len = slice.len();
let mut table = slice.to_vec();
table.extend(slice.iter().cloned());
let mut table = table.into_boxed_slice();
(1..len)
.rev()
.for_each(|i| table[i] = op(table[2 * i].clone(), table[2 * i + 1].clone()));
Self {
len,
table,
op,
identity,
}
}
pub fn as_slice(&self) -> &[T] {
&self.table[self.len..]
}
pub fn entry(&mut self, index: usize) -> Entry<'_, T, Op, Identity> {
Entry { seg: self, index }
}
pub fn fold(&self, range: impl RangeBounds<usize>) -> T {
let Range { mut start, mut end } = open(range, self.len);
start += self.len;
end += self.len;
let mut fl = (self.identity)();
let mut fr = (self.identity)();
while start != end {
if start % 2 == 1 {
fl = (self.op)(fl, self.table[start].clone());
start += 1;
}
if end % 2 == 1 {
end -= 1;
fr = (self.op)(self.table[end].clone(), fr);
}
start /= 2;
end /= 2;
}
(self.op)(fl, fr)
}
pub fn search_forward(
&self,
range: impl RangeBounds<usize>,
mut pred: impl FnMut(&T) -> bool,
) -> usize {
let Range { mut start, mut end } = open(range, self.len);
if start == end {
start
} else {
start += self.len;
end += self.len;
let orig_end = end;
let mut crr = (self.identity)();
let mut shift = 0;
while start != end {
if start % 2 == 1 {
let nxt = (self.op)(crr.clone(), self.table[start].clone());
if !pred(&nxt) {
return self.search_subtree_forward(crr, start, pred);
}
crr = nxt;
start += 1;
}
start >>= 1;
end >>= 1;
shift += 1;
}
for p in (0..shift).rev() {
let end = (orig_end >> p) - 1;
if end % 2 == 0 {
let nxt = (self.op)(crr.clone(), self.table[end].clone());
if !pred(&nxt) {
return self.search_subtree_forward(crr, end, pred);
}
crr = nxt;
}
}
orig_end - self.len
}
}
pub fn search_backward(
&self,
range: impl RangeBounds<usize>,
mut pred: impl FnMut(&T) -> bool,
) -> usize {
let Range { mut start, mut end } = open(range, self.len);
if start == end {
start
} else {
start += self.len;
end += self.len;
let orig_start_m1 = start - 1;
let mut crr = (self.identity)();
let mut shift = 0;
while start != end {
if end % 2 == 1 {
end -= 1;
let nxt = (self.op)(self.table[end].clone(), crr.clone());
if !pred(&nxt) {
return self.search_subtree_backward(crr, end, pred);
}
crr = nxt;
}
start = (start + 1) >> 1;
end >>= 1;
shift += 1;
}
for p in (0..shift).rev() {
let start = (orig_start_m1 >> p) + 1;
if start % 2 == 1 {
let nxt = (self.op)(self.table[start].clone(), crr.clone());
if !pred(&nxt) {
return self.search_subtree_backward(crr, start, pred);
}
crr = nxt;
}
}
orig_start_m1 + 1 - self.len
}
}
fn search_subtree_forward(
&self,
mut crr: T,
mut root: usize,
mut pred: impl FnMut(&T) -> bool,
) -> usize {
while root < self.len {
let nxt = (self.op)(crr.clone(), self.table[root * 2].clone());
root = if pred(&nxt) {
crr = nxt;
root * 2 + 1
} else {
root * 2
};
}
root - self.len
}
fn search_subtree_backward(
&self,
mut crr: T,
mut root: usize,
mut pred: impl FnMut(&T) -> bool,
) -> usize {
while root < self.len {
let nxt = (self.op)(self.table[root * 2 + 1].clone(), crr.clone());
root = if pred(&nxt) {
crr = nxt;
root * 2
} else {
root * 2 + 1
};
}
root + 1 - self.len
}
}
fn open(range: impl RangeBounds<usize>, len: usize) -> Range<usize> {
(match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(&x) => x,
Bound::Excluded(&x) => x + 1,
})..match range.end_bound() {
Bound::Excluded(&x) => x,
Bound::Included(&x) => x + 1,
Bound::Unbounded => len,
}
}
impl<T: Debug, Op, Identity> Debug for Segtree<T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
fn fmt(&self, w: &mut Formatter<'_>) -> fmt::Result {
w.debug_tuple("Segtree")
.field(&&self.table[self.len..])
.finish()
}
}
impl<I: SliceIndex<[T]>, T, Op, Identity> Index<I> for Segtree<T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
type Output = I::Output;
fn index(&self, index: I) -> &I::Output {
&self.as_slice()[index]
}
}
pub struct Entry<'a, T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
seg: &'a mut Segtree<T, Op, Identity>,
index: usize,
}
impl<'a, T, Op, Identity> Drop for Entry<'a, T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
fn drop(&mut self) {
let mut index = self.index + self.seg.len;
while index != 0 {
index /= 2;
self.seg.table[index] = (self.seg.op)(
self.seg.table[index * 2].clone(),
self.seg.table[index * 2 + 1].clone(),
);
}
}
}
impl<'a, T, Op, Identity> Deref for Entry<'a, T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
type Target = T;
fn deref(&self) -> &Self::Target {
&self.seg[self.index]
}
}
impl<'a, T, Op, Identity> DerefMut for Entry<'a, T, Op, Identity>
where
T: Clone,
Op: Fn(T, T) -> T,
Identity: Fn() -> T,
{
fn deref_mut(&mut self) -> &mut Self::Target {
let index = self.index;
let len = self.seg.len;
&mut (self.seg.table[len..])[index]
}
}
}
// }}}
// union_find {{{
#[allow(dead_code)]
mod union_find {
use std::{
cell::RefCell,
fmt::{Debug, Formatter, Result},
mem::swap,
};
#[derive(Clone)]
pub struct UnionFind(RefCell<Vec<isize>>);
impl UnionFind {
pub fn new(len: usize) -> Self {
Self(RefCell::new(vec![-1; len]))
}
pub fn is_empty(&self) -> bool {
self.0.borrow().is_empty()
}
pub fn len(&self) -> usize {
self.0.borrow().len()
}
pub fn push(&mut self) {
self.0.borrow_mut().push(-1);
}
pub fn find(&self, i: usize) -> usize {
self.find_and_size(i)[0]
}
pub fn size(&self, i: usize) -> usize {
self.find_and_size(i)[1]
}
pub fn union(&mut self, u: usize, v: usize) {
let [mut u, su] = self.find_and_size(u);
let [mut v, sv] = self.find_and_size(v);
if u == v {
return;
}
if su > sv {
swap(&mut u, &mut v);
}
let mut table = self.0.borrow_mut();
table[v] = -((su + sv) as isize);
table[u] = v as isize;
}
pub fn same(&self, u: usize, v: usize) -> bool {
self.find(u) == self.find(v)
}
pub fn is_root(&self, u: usize) -> bool {
self.find(u) == u
}
fn find_and_size(&self, mut x: usize) -> [usize; 2] {
assert!(x < self.0.borrow().len());
let mut child = Vec::new();
loop {
let elm = self.0.borrow()[x];
x = match elm {
p if 0 <= p => p as usize,
elm => {
let sz = (-elm) as usize;
let mut table = self.0.borrow_mut();
child
.iter()
.copied()
.filter(|&y| x != y)
.for_each(|y| table[y] = x as isize);
return [x, sz];
}
};
child.push(x);
}
}
}
impl Debug for UnionFind {
fn fmt(&self, f: &mut Formatter<'_>) -> Result {
use std::collections::HashMap;
let mut map = HashMap::new();
for i in 0..self.len() {
map.entry(self.find(i)).or_insert_with(Vec::new).push(i);
}
f.debug_list().entries(map.values()).finish()
}
}
}
// }}}
// ngtio {{{
#[allow(dead_code)]
mod ngtio {
mod i {
use std::{
io::{self, BufRead},
iter,
};
pub use self::{
multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen},
token::{Token, Usize1},
};
pub fn with_stdin() -> Tokenizer<io::BufReader<io::Stdin>> {
io::BufReader::new(io::stdin()).tokenizer()
}
pub fn with_str(src: &str) -> Tokenizer<&[u8]> {
src.as_bytes().tokenizer()
}
pub struct Tokenizer<S: BufRead> {
queue: Vec<String>, // FIXME: String のみにすると速そうです。
scanner: S,
}
macro_rules! prim_method {
($name:ident: $T:ty) => {
pub fn $name(&mut self) -> $T {
<$T>::leaf().parse(self)
}
};
($name:ident) => {
prim_method!($name: $name);
};
}
macro_rules! prim_methods {
($name:ident: $T:ty; $($rest:tt)*) => {
prim_method!($name:$T);
prim_methods!($($rest)*);
};
($name:ident; $($rest:tt)*) => {
prim_method!($name);
prim_methods!($($rest)*);
};
() => ()
}
impl<S: BufRead> Tokenizer<S> {
pub fn token(&mut self) -> String {
self.load();
self.queue.pop().expect("入力が終了したのですが。")
}
pub fn new(scanner: S) -> Self {
Self {
queue: Vec::new(),
scanner,
}
}
fn load(&mut self) {
while self.queue.is_empty() {
let mut s = String::new();
let length = self.scanner.read_line(&mut s).unwrap(); // 入力が UTF-8 でないときにエラーだそうです。
if length == 0 {
break;
}
self.queue = s.split_whitespace().rev().map(str::to_owned).collect();
}
}
pub fn skip_line(&mut self) {
assert!(
self.queue.is_empty(),
"行の途中で呼ばないでいただきたいです。現在のトークンキュー: {:?}",
&self.queue
);
self.load();
}
pub fn end(&mut self) {
self.load();
assert!(self.queue.is_empty(), "入力はまだあります！");
}
pub fn parse<T: Token>(&mut self) -> T::Output {
T::parse(&self.token())
}
pub fn parse_collect<T: Token, B>(&mut self, n: usize) -> B
where
B: iter::FromIterator<T::Output>,
{
iter::repeat_with(|| self.parse::<T>()).take(n).collect()
}
pub fn tuple<T: RawTuple>(&mut self) -> <T::LeafTuple as Parser>::Output {
T::leaf_tuple().parse(self)
}
pub fn vec<T: Token>(&mut self, len: usize) -> Vec<T::Output> {
T::leaf().vec(len).parse(self)
}
pub fn vec_tuple<T: RawTuple>(
&mut self,
len: usize,
) -> Vec<<T::LeafTuple as Parser>::Output> {
T::leaf_tuple().vec(len).parse(self)
}
pub fn vec2<T: Token>(&mut self, height: usize, width: usize) -> Vec<Vec<T::Output>> {
T::leaf().vec(width).vec(height).parse(self)
}
pub fn vec2_tuple<T>(
&mut self,
height: usize,
width: usize,
) -> Vec<Vec<<T::LeafTuple as Parser>::Output>>
where
T: RawTuple,
{
T::leaf_tuple().vec(width).vec(height).parse(self)
}
prim_methods! {
u8; u16; u32; u64; u128; usize;
i8; i16; i32; i64; i128; isize;
f32; f64;
char; string: String;
}
}
mod token {
use super::multi_token::Leaf;
use std::{any, fmt, marker, str};
pub trait Token: Sized {
type Output;
fn parse(s: &str) -> Self::Output;
fn leaf() -> Leaf<Self> {
Leaf(marker::PhantomData)
}
}
impl<T> Token for T
where
T: str::FromStr,
<Self as str::FromStr>::Err: fmt::Debug,
{
type Output = Self;
fn parse(s: &str) -> Self::Output {
s.parse().unwrap_or_else(|_| {
panic!("Parse error!: ({}: {})", s, any::type_name::<Self>(),)
})
}
}
pub struct Usize1 {}
impl Token for Usize1 {
type Output = usize;
fn parse(s: &str) -> Self::Output {
usize::parse(s)
.checked_sub(1)
.expect("Parse error! (Zero substruction error of Usize1)")
}
}
}
mod multi_token {
use super::{Token, Tokenizer};
use std::{io::BufRead, iter, marker};
pub trait Parser: Sized {
type Output;
fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output;
fn vec(self, len: usize) -> VecLen<Self> {
VecLen { len, elem: self }
}
}
pub struct Leaf<T>(pub(super) marker::PhantomData<T>);
impl<T: Token> Parser for Leaf<T> {
type Output = T::Output;
fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> T::Output {
server.parse::<T>()
}
}
pub struct VecLen<T> {
pub len: usize,
pub elem: T,
}
impl<T: Parser> Parser for VecLen<T> {
type Output = Vec<T::Output>;
fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output {
iter::repeat_with(|| self.elem.parse(server))
.take(self.len)
.collect()
}
}
pub trait RawTuple {
type LeafTuple: Parser;
fn leaf_tuple() -> Self::LeafTuple;
}
pub trait ParserTuple {
type Tuple: Parser;
fn tuple(self) -> Self::Tuple;
}
pub struct Tuple<T>(pub T);
macro_rules! impl_tuple {
($($t:ident: $T:ident),*) => {
impl<$($T),*> Parser for Tuple<($($T,)*)>
where
$($T: Parser,)*
{
type Output = ($($T::Output,)*);
#[allow(unused_variables)]
fn parse<S: BufRead >(&self, server: &mut Tokenizer<S>) -> Self::Output {
match self {
Tuple(($($t,)*)) => {
($($t.parse(server),)*)
}
}
}
}
impl<$($T: Token),*> RawTuple for ($($T,)*) {
type LeafTuple = Tuple<($(Leaf<$T>,)*)>;
fn leaf_tuple() -> Self::LeafTuple {
Tuple(($($T::leaf(),)*))
}
}
impl<$($T: Parser),*> ParserTuple for ($($T,)*) {
type Tuple = Tuple<($($T,)*)>;
fn tuple(self) -> Self::Tuple {
Tuple(self)
}
}
};
}
impl_tuple!();
impl_tuple!(t1: T1);
impl_tuple!(t1: T1, t2: T2);
impl_tuple!(t1: T1, t2: T2, t3: T3);
impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4);
impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5);
impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6);
impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7);
impl_tuple!(
t1: T1,
t2: T2,
t3: T3,
t4: T4,
t5: T5,
t6: T6,
t7: T7,
t8: T8
);
}
trait Scanner: BufRead + Sized {
fn tokenizer(self) -> Tokenizer<Self> {
Tokenizer::new(self)
}
}
impl<R: BufRead> Scanner for R {}
}
pub use self::i::{with_stdin, with_str};
pub mod prelude {
pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1};
}
}
// }}}