結果

問題 No.3056 Disconnected Coloring
ユーザー magurofly
提出日時 2025-03-14 23:14:43
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 10,090 bytes
コンパイル時間 20,479 ms
コンパイル使用メモリ 401,996 KB
実行使用メモリ 97,584 KB
最終ジャッジ日時 2025-03-14 23:15:17
合計ジャッジ時間 30,180 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 WA * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `flow`
  --> src/main.rs:46:9
   |
46 |     let flow = flow_graph.flow(0, n - 1);
   |         ^^^^ help: if this is intentional, prefix it with an underscore: `_flow`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use std::collections::VecDeque;

use acl_maxflow::MfGraph;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize, m: usize,
        edges: [(Usize1, Usize1); m],
    }

    let mut graph = vec![vec![]; n];
    for e in 0..m {
        let (u, v) = edges[e];
        graph[u].push((v, e));
        graph[v].push((u, e));
    }

    let mut queue = VecDeque::new();
    let mut dist = vec![n; n];
    dist[0] = 0;
    queue.push_back(0);
    while let Some(u) = queue.pop_front() {
        for &(v, _) in &graph[u] {
            if dist[v] <= dist[u] + 1 {
                continue;
            }
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }

    if dist[n - 1] <= 1 || m % 2 != 0 {
        println!("-1");
        return;
    }

    let mut flow_graph = MfGraph::<usize>::new(n);
    for &(u, v) in &edges {
        flow_graph.add_edge(u, v, n);
        flow_graph.add_edge(v, u, n);
    }

    let flow = flow_graph.flow(0, n - 1);
    let mut color = vec!['.'; m];
    let mut count = [0, 0];

    for &(_, e) in &graph[0] {
        if flow_graph.get_edge(2 * e).flow > 0 {
            color[e] = 'R';
            count[0] += 1;
        }
    }

    for &(_, e) in &graph[n - 1] {
        if flow_graph.get_edge(2 * e + 1).flow > 0 {
            color[e] = 'B';
            count[1] += 1;
        }
    }

    for e in 0..m {
        if color[e] == '.' {
            if count[0] < count[1] {
                color[e] = 'R';
                count[0] += 1;
            } else {
                color[e] = 'B';
                count[1] += 1;
            }
        }
    }

    println!("{}", color.into_iter().collect::<String>());
}
// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `ac-library-rs-parted-internal-queue 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████████████████████████)`             published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_queue_0_1_0`
///  - `ac-library-rs-parted-internal-type-traits 0.1.0 (path+███████████████████████████████████████████████████████████████████████████████████████████████████████)` published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_type_traits_0_1_0`
///  - `ac-library-rs-parted-maxflow 0.1.0 (path+██████████████████████████████████████████████████████████████████████████████████████████)`                           published in https://github.com/qryxip/ac-library-rs-parted licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_maxflow`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __ac_library_rs_parted_internal_queue_0_1_0 {pub use self::internal_queue::*;mod internal_queue{#![allow(dead_code)]#[derive(Default)]pub struct SimpleQueue<T>{payload:Vec<T>,pos:usize,}impl<T>SimpleQueue<T>{pub fn reserve(&mut self,n:usize){if n>self.payload.len(){self.payload.reserve(n-self.payload.len());}}pub fn size(&self)->usize{self.payload.len()-self.pos}pub fn empty(&self)->bool{self.pos==self.payload.len()}pub fn push(&mut self,t:T){self.payload.push(t);}pub fn front(&self)->Option<&T>{if self.pos<self.payload.len(){Some(&self.payload[self.pos])}else{None}}pub fn clear(&mut self){self.payload.clear();self.pos=0;}pub fn pop(&mut self)->Option<&T>{if self.pos<self.payload.len(){self.pos+=1;Some(&self.payload[self.pos-1])}else{None}}}}}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {pub use self::internal_type_traits::*;mod internal_type_traits{use std::{fmt,iter::{Product,Sum},ops::{Add,AddAssign,BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Div,DivAssign,Mul,MulAssign,Not,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},};pub trait Integral:'static+Send+Sync+Copy+Ord+Not<Output=Self>+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+Rem<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+RemAssign+Sum+Product+BitOr<Output=Self>+BitAnd<Output=Self>+BitXor<Output=Self>+BitOrAssign+BitAndAssign+BitXorAssign+Shl<Output=Self>+Shr<Output=Self>+ShlAssign+ShrAssign+fmt::Display+fmt::Debug+fmt::Binary+fmt::Octal+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::min_value()}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::max_value()}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}}
        pub mod acl_maxflow {use crate::__cargo_equip::preludes::acl_maxflow::*;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_queue_0_1_0 as internal_queue;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_type_traits_0_1_0 as internal_type_traits;pub use self::maxflow::*;mod maxflow{#![allow(dead_code)]use crate::__cargo_equip::preludes::acl_maxflow::*;use super::internal_queue::SimpleQueue;use super::internal_type_traits::Integral;use std::cmp::min;use std::iter;impl<Cap>MfGraph<Cap>where Cap:Integral,{pub fn new(n:usize)->MfGraph<Cap>{MfGraph{_n:n,pos:Vec::new(),g:iter::repeat_with(Vec::new).take(n).collect(),}}pub fn add_edge(&mut self,from:usize,to:usize,cap:Cap)->usize{assert!(from<self._n);assert!(to<self._n);assert!(Cap::zero()<=cap);let m=self.pos.len();self.pos.push((from,self.g[from].len()));let rev=self.g[to].len()+if from==to{1}else{0};self.g[from].push(_Edge{to,rev,cap});let rev=self.g[from].len()-1;self.g[to].push(_Edge{to:from,rev,cap:Cap::zero(),});m}}#[derive(Debug,PartialEq,Eq)]pub struct Edge<Cap:Integral>{pub from:usize,pub to:usize,pub cap:Cap,pub flow:Cap,}impl<Cap>MfGraph<Cap>where Cap:Integral,{pub fn get_edge(&self,i:usize)->Edge<Cap>{let m=self.pos.len();assert!(i<m);let _e=&self.g[self.pos[i].0][self.pos[i].1];let _re=&self.g[_e.to][_e.rev];Edge{from:self.pos[i].0,to:_e.to,cap:_e.cap+_re.cap,flow:_re.cap,}}pub fn edges(&self)->Vec<Edge<Cap>>{let m=self.pos.len();(0..m).map(|i|self.get_edge(i)).collect()}pub fn change_edge(&mut self,i:usize,new_cap:Cap,new_flow:Cap){let m=self.pos.len();assert!(i<m);assert!(Cap::zero()<=new_flow&&new_flow<=new_cap);let(to,rev)={let _e=&mut self.g[self.pos[i].0][self.pos[i].1];_e.cap=new_cap-new_flow;(_e.to,_e.rev)};let _re=&mut self.g[to][rev];_re.cap=new_flow;}pub fn flow(&mut self,s:usize,t:usize)->Cap{self.flow_with_capacity(s,t,Cap::max_value())}pub fn flow_with_capacity(&mut self,s:usize,t:usize,flow_limit:Cap)->Cap{let n_=self._n;assert!(s<n_);assert!(t<n_);assert_ne!(s,t);assert!(Cap::zero()<=flow_limit);let mut calc=FlowCalculator{graph:self,s,t,flow_limit,level:vec![0;n_],iter:vec![0;n_],que:SimpleQueue::default(),};let mut flow=Cap::zero();while flow<flow_limit{calc.bfs();if calc.level[t]==-1{break;}calc.iter.iter_mut().for_each(|e|*e=0);while flow<flow_limit{let f=calc.dfs(t,flow_limit-flow);if f==Cap::zero(){break;}flow+=f;}}flow}pub fn min_cut(&self,s:usize)->Vec<bool>{let mut visited=vec![false;self._n];let mut que=SimpleQueue::default();que.push(s);while let Some(&p)=que.pop(){visited[p]=true;for e in&self.g[p]{if e.cap!=Cap::zero()&&!visited[e.to]{visited[e.to]=true;que.push(e.to);}}}visited}}struct FlowCalculator<'a,Cap>{graph:&'a mut MfGraph<Cap>,s:usize,t:usize,flow_limit:Cap,level:Vec<i32>,iter:Vec<usize>,que:SimpleQueue<usize>,}impl<Cap>FlowCalculator<'_,Cap>where Cap:Integral,{fn bfs(&mut self){self.level.iter_mut().for_each(|e|*e=-1);self.level[self.s]=0;self.que.clear();self.que.push(self.s);while!self.que.empty(){let v=*self.que.front().unwrap();self.que.pop();for e in&self.graph.g[v]{if e.cap==Cap::zero()||self.level[e.to]>=0{continue;}self.level[e.to]=self.level[v]+1;if e.to==self.t{return;}self.que.push(e.to);}}}fn dfs(&mut self,v:usize,up:Cap)->Cap{if v==self.s{return up;}let mut res=Cap::zero();let level_v=self.level[v];for i in self.iter[v]..self.graph.g[v].len(){self.iter[v]=i;let&_Edge{to:e_to,rev:e_rev,..}=&self.graph.g[v][i];if level_v<=self.level[e_to]||self.graph.g[e_to][e_rev].cap==Cap::zero(){continue;}let d=self.dfs(e_to,min(up-res,self.graph.g[e_to][e_rev].cap));if d<=Cap::zero(){continue;}self.graph.g[v][i].cap+=d;self.graph.g[e_to][e_rev].cap-=d;res+=d;if res==up{return res;}}self.iter[v]=self.graph.g[v].len();res}}#[derive(Default)]pub struct MfGraph<Cap>{_n:usize,pos:Vec<(usize,usize)>,g:Vec<Vec<_Edge<Cap>>>,}struct _Edge<Cap>{to:usize,rev:usize,cap:Cap,}}}
    }

    pub(crate) mod macros {
        pub mod __ac_library_rs_parted_internal_queue_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {}
        pub mod acl_maxflow {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod __ac_library_rs_parted_internal_queue_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {}
        pub mod acl_maxflow {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_queue_0_1_0 as __acl_internal_queue,__ac_library_rs_parted_internal_type_traits_0_1_0 as __acl_internal_type_traits};}
    }
}
0