結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー koba-e964
提出日時 2021-11-17 20:36:30
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 10,328 bytes
コンパイル時間 14,626 ms
コンパイル使用メモリ 378,288 KB
実行使用メモリ 48,752 KB
最終ジャッジ日時 2024-12-24 01:31:24
合計ジャッジ時間 21,479 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 17 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes.by_ref().map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
macro_rules! input_inner {
($next:expr) => {};
($next:expr,) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}
/// Verified by https://atcoder.jp/contests/abc198/submissions/21774342
mod mod_int {
use std::ops::*;
pub trait Mod: Copy { fn m() -> i64; }
#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct ModInt<M> { pub x: i64, phantom: ::std::marker::PhantomData<M> }
impl<M: Mod> ModInt<M> {
// x >= 0
pub fn new(x: i64) -> Self { ModInt::new_internal(x % M::m()) }
fn new_internal(x: i64) -> Self {
ModInt { x: x, phantom: ::std::marker::PhantomData }
}
pub fn pow(self, mut e: i64) -> Self {
debug_assert!(e >= 0);
let mut sum = ModInt::new_internal(1);
let mut cur = self;
while e > 0 {
if e % 2 != 0 { sum *= cur; }
cur *= cur;
e /= 2;
}
sum
}
#[allow(dead_code)]
pub fn inv(self) -> Self { self.pow(M::m() - 2) }
}
impl<M: Mod> Default for ModInt<M> {
fn default() -> Self { Self::new_internal(0) }
}
impl<M: Mod, T: Into<ModInt<M>>> Add<T> for ModInt<M> {
type Output = Self;
fn add(self, other: T) -> Self {
let other = other.into();
let mut sum = self.x + other.x;
if sum >= M::m() { sum -= M::m(); }
ModInt::new_internal(sum)
}
}
impl<M: Mod, T: Into<ModInt<M>>> Sub<T> for ModInt<M> {
type Output = Self;
fn sub(self, other: T) -> Self {
let other = other.into();
let mut sum = self.x - other.x;
if sum < 0 { sum += M::m(); }
ModInt::new_internal(sum)
}
}
impl<M: Mod, T: Into<ModInt<M>>> Mul<T> for ModInt<M> {
type Output = Self;
fn mul(self, other: T) -> Self { ModInt::new(self.x * other.into().x % M::m()) }
}
impl<M: Mod, T: Into<ModInt<M>>> AddAssign<T> for ModInt<M> {
fn add_assign(&mut self, other: T) { *self = *self + other; }
}
impl<M: Mod, T: Into<ModInt<M>>> SubAssign<T> for ModInt<M> {
fn sub_assign(&mut self, other: T) { *self = *self - other; }
}
impl<M: Mod, T: Into<ModInt<M>>> MulAssign<T> for ModInt<M> {
fn mul_assign(&mut self, other: T) { *self = *self * other; }
}
impl<M: Mod> Neg for ModInt<M> {
type Output = Self;
fn neg(self) -> Self { ModInt::new(0) - self }
}
impl<M> ::std::fmt::Display for ModInt<M> {
fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
self.x.fmt(f)
}
}
impl<M: Mod> ::std::fmt::Debug for ModInt<M> {
fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
let (mut a, mut b, _) = red(self.x, M::m());
if b < 0 {
a = -a;
b = -b;
}
write!(f, "{}/{}", a, b)
}
}
impl<M: Mod> From<i64> for ModInt<M> {
fn from(x: i64) -> Self { Self::new(x) }
}
// Finds the simplest fraction x/y congruent to r mod p.
// The return value (x, y, z) satisfies x = y * r + z * p.
fn red(r: i64, p: i64) -> (i64, i64, i64) {
if r.abs() <= 10000 {
return (r, 1, 0);
}
let mut nxt_r = p % r;
let mut q = p / r;
if 2 * nxt_r >= r {
nxt_r -= r;
q += 1;
}
if 2 * nxt_r <= -r {
nxt_r += r;
q -= 1;
}
let (x, z, y) = red(nxt_r, r);
(x, y - q * z, z)
}
} // mod mod_int
macro_rules! define_mod {
($struct_name: ident, $modulo: expr) => {
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct $struct_name {}
impl mod_int::Mod for $struct_name { fn m() -> i64 { $modulo } }
}
}
const MOD: i64 = 1_000_000_007;
define_mod!(P, MOD);
type MInt = mod_int::ModInt<P>;
// Strong connected components.
// Verified by: yukicoder No.470 (http://yukicoder.me/submissions/145785)
// ABC214-H (https://atcoder.jp/contests/abc214/submissions/25082618)
struct SCC {
n: usize,
ncc: usize,
g: Vec<Vec<usize>>, // graph in adjacent list
rg: Vec<Vec<usize>>, // reverse graph
cmp: Vec<usize>, // topological order
}
impl SCC {
fn new(n: usize) -> Self {
SCC {
n: n,
ncc: n + 1,
g: vec![Vec::new(); n],
rg: vec![Vec::new(); n],
cmp: vec![0; n],
}
}
fn add_edge(&mut self, from: usize, to: usize) {
self.g[from].push(to);
self.rg[to].push(from);
}
fn dfs(&self, v: usize, used: &mut [bool], vs: &mut Vec<usize>) {
used[v] = true;
for &w in self.g[v].iter() {
if !used[w] {
self.dfs(w, used, vs);
}
}
vs.push(v);
}
fn rdfs(&self, v: usize, k: usize,
used: &mut [bool], cmp: &mut [usize]) {
used[v] = true;
cmp[v] = k;
for &w in self.rg[v].iter() {
if !used[w] {
self.rdfs(w, k, used, cmp);
}
}
}
fn scc(&mut self) -> usize {
let n = self.n;
let mut used = vec![false; n];
let mut vs = Vec::new();
let mut cmp = vec![0; n];
for v in 0 .. n {
if !used[v] { self.dfs(v, &mut used, &mut vs); }
}
for u in used.iter_mut() {
*u = false;
}
let mut k = 0;
for &t in vs.iter().rev() {
if !used[t] { self.rdfs(t, k, &mut used, &mut cmp); k += 1; }
}
self.ncc = k;
self.cmp = cmp;
k
}
#[allow(dead_code)]
fn top_order(&self) -> Vec<usize> {
assert!(self.ncc <= self.n);
self.cmp.clone()
}
/*
* Returns a dag whose vertices are scc's, and whose edges are those of the original graph.
*/
#[allow(dead_code)]
fn dag(&self) -> Vec<Vec<usize>> {
assert!(self.ncc <= self.n);
let ncc = self.ncc;
let mut ret = vec![vec![]; ncc];
let n = self.n;
for i in 0 .. n {
for &to in self.g[i].iter() {
if self.cmp[i] != self.cmp[to] {
assert!(self.cmp[i] < self.cmp[to]);
ret[self.cmp[i]].push(self.cmp[to]);
}
}
}
ret.into_iter().map(|mut v| {
v.sort_unstable(); v.dedup();
v
}).collect()
}
#[allow(dead_code)]
fn rdag(&self) -> Vec<Vec<usize>> {
assert!(self.ncc <= self.n);
let ncc = self.ncc;
let mut ret = vec![vec![]; ncc];
let n = self.n;
for i in 0 .. n {
for &to in self.g[i].iter() {
if self.cmp[i] != self.cmp[to] {
assert!(self.cmp[i] < self.cmp[to]);
ret[self.cmp[to]].push(self.cmp[i]);
}
}
}
ret.into_iter().map(|mut v| {
v.sort_unstable(); v.dedup();
v
}).collect()
}
}
trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); }
impl<T: PartialOrd> Change for T {
fn chmax(&mut self, x: T) { if *self < x { *self = x; } }
fn chmin(&mut self, x: T) { if *self > x { *self = x; } }
}
fn main() {
// In order to avoid potential stack overflow, spawn a new thread.
let stack_size = 104_857_600; // 100 MB
let thd = std::thread::Builder::new().stack_size(stack_size);
thd.spawn(|| solve()).unwrap().join().unwrap();
}
fn reach(v: usize, g: &[Vec<usize>]) -> Vec<bool> {
let n = g.len();
let mut vis = vec![false; n];
let mut que = vec![v];
while let Some(v) = que.pop() {
if vis[v] { continue; }
vis[v] = true;
for &w in &g[v] {
que.push(w);
}
}
vis
}
fn dfs(v: usize, g: &[Vec<(usize, i64, i64)>], vis: &mut [bool],
dp: &mut [(MInt, MInt)]) {
if vis[v] { return; }
let n = g.len();
if v == n - 1 {
dp[v] = (1.into(), 0.into());
vis[v] = true;
return;
}
let mut x = MInt::new(0);
let mut y = MInt::new(0);
for &(w, l, a) in &g[v] {
dfs(w, g, vis, dp);
x += dp[w].0 * a;
y += (dp[w].1 + dp[w].0 * l) * a;
}
dp[v] = (x, y);
vis[v] = true;
}
fn solve() {
input! {
n: usize, m: usize,
uvla: [(usize, usize, i64, i64); m],
}
let mut scc = SCC::new(n + 1);
for &(u, v, _, _) in &uvla {
scc.add_edge(u, v);
}
let ncc = scc.scc();
let top_ord = scc.top_order();
let v1 = reach(top_ord[0], &scc.dag());
let v2 = reach(top_ord[n - 1], &scc.rdag());
let mut sz = vec![0; ncc];
for i in 0..n + 1 {
sz[top_ord[i]] += 1;
}
for i in 0..ncc {
if v1[i] && v2[i] && sz[i] >= 2 {
println!("INF");
return;
}
}
let mut dp = vec![(MInt::new(0), MInt::new(0)); n + 1];
let mut vis = vec![false; n + 1];
let mut g = vec![vec![]; n + 1];
for &(u, v, l, a) in &uvla {
let nu = top_ord[u];
let nv = top_ord[v];
if !v1[nu] || !v2[nu] || !v1[nv] || !v2[nv] { continue; }
g[u].push((v, l, a));
}
dfs(0, &g, &mut vis, &mut dp);
println!("{}", dp[n].1);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0