#932147 (Rust) No.2596 Christmas Eve (Heuristic ver.)

提出ソース

結果

問題	No.2596 Christmas Eve (Heuristic ver.)
ユーザー	rhoo
提出日時	2023-11-27 21:07:31
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	54 ms / 1,224 ms
コード長	10,160 bytes
コンパイル時間	1,673 ms
コンパイル使用メモリ	200,472 KB
実行使用メモリ	38,960 KB
スコア	2,509,570
最終ジャッジ日時	2023-12-23 20:30:38
合計ジャッジ時間	18,362 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 125

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: constant `INF` is never used
   --> Main.rs:148:7
    |
148 | const INF:Flow=Flow::MAX/4;
    |       ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function `solve_dinic` is never used
   --> Main.rs:160:4
    |
160 | fn solve_dinic(g:&mut G<Edge>,s:usize,t:usize)->Flow{
    |    ^^^^^^^^^^^

warning: function `restore_mincut` is never used
   --> Main.rs:247:4
    |
247 | fn restore_mincut(g:&G<Edge>,s:usize)->Vec<bool>{
    |    ^^^^^^^^^^^^^^

warning: methods `change_edge`, `get_cap`, `restore_mincut`, and `solve` are never used
   --> Main.rs:290:8
    |
270 | impl MaxFlow{
    | ------------ methods in this implementation
...
290 |     fn change_edge(&mut self,id:usize,new_flow:Flow,new_cap:Flow){
    |        ^^^^^^^^^^^
...
298 |     fn get_cap(&self,id:usize)->Flow{
    |        ^^^^^^^
...
310 |     fn restore_mincut(&self,s:usize)->Vec<bool>{
    |        ^^^^^^^^^^^^^^
...
314 |     fn solve(&mut self,s:usize,t:usize)->Flow{
    |        ^^^^^

warning: methods `is_empty`, `len`, `front`, and `to_slice` are never used
   --> Main.rs:344:8
    |
331 | impl<T> Queue<T>{
    | ---------------- methods in this implementation
...
344 |     fn is_empty(&self)->bool{
    |        ^^^^^^^^
...
348 |     fn len(&self)->usize{
    |        ^^^
...
365 |     fn front(&self)->Option<&T>{
    |        ^^^^^
...
373 |     fn to_slice(&self)->&[T]{
    |        ^^^^^^^^

warning: 5 warnings emitted

ソースコード

raw source code

#![allow(non_snake_case)]


fn main(){
    let input=Input::new();
    let ans=solve(&input);

    check_output(&input,&ans);

    for t in &ans{
        println!("{} {} {} {}",t.0+1,t.1+1,t.2+1,t.3+1);
    }
}


fn solve(input:&Input)->Vec<(usize,usize,usize,usize)>{
    let mut low=input.low.clone();
    low.sort_by_key(|t|!t.1);

    let mut g=MaxFlow::new(4*N+2);
    let s=4*N;
    let t=s+1;

    let mut edge=vec![(vec![],vec![]);N];

    for i in 0..N{
        g.add_edge(s,i,1);
        g.add_edge(N+i,2*N+i,1);
        g.add_edge(3*N+i,t,1);

        for j in 0..N{
            if low[i*2+1].1>input.mid[j].1{
                let id=g.add_edge(i,j+N,1);
                edge[j].0.push((id,i*2+1));
            }
            if input.mid[i].1>input.top[j].1{
                let id=g.add_edge(i+2*N,j+3*N,1);
                edge[i].1.push((id,j));
            }
        }
    }

    
    let f=g.solve_with_capacity(s,t,input.K);
    assert!(f==input.K);

    let mut ans=vec![];
    for i in 0..N{
        let Some(&a)=edge[i].0.iter().find(|&t|g.get_flow(t.0)>0) else{continue};
        let b=edge[i].1.iter().find(|&t|g.get_flow(t.0)>0).unwrap();

        ans.push((i,low[a.1-1].0,low[a.1].0,b.1));
    }

    assert!(ans.len()==input.K);

    ans
}


type G<T>=Vec<Vec<(usize,T)>>;


const N:usize=500;


struct Input{
    K:usize,
    low:Vec<(usize,i64,i64)>, // id,width,height
    mid:Vec<(usize,i64,i64)>,
    top:Vec<(usize,i64,i64)>,
}
impl Input{
    fn new()->Input{
        let mut scan=Scanner::new();
        let n:usize=scan.read();
        assert!(n==N);

        let K:usize=scan.read();
        assert!((300..=400).contains(&K));

        let mut read_vec=|n|(0..n).map(|_|{
            let a:i64=scan.read();
            assert!((1..=10000).contains(&a));
            a
        }).collect::<Vec<_>>();

        let (a,b)=(read_vec(n),read_vec(n));
        let (c,d)=(read_vec(2*n),read_vec(2*n));
        let (e,f)=(read_vec(n),read_vec(n));

        Input{
            K,
            low:(0..2*n).map(|i|(i,c[i],d[i])).collect(),
            mid:(0..n).map(|i|(i,a[i],b[i])).collect(),
            top:(0..n).map(|i|(i,e[i],f[i])).collect(),
        }
    }
}



fn check_output(input:&Input,ans:&[(usize,usize,usize,usize)]){
    assert!(ans.len()==input.K);

    let mut cnt=vec![0;N*4];
    for &t in ans{
        cnt[t.0]+=1;
        cnt[t.1+N]+=1;
        cnt[t.2+N]+=1;
        cnt[t.3+N*3]+=1;
    }
    assert!(cnt.iter().all(|&t|t<=1));

    for &t in ans{
        assert!(input.mid[t.0].1<input.low[t.1].1.min(input.low[t.2].1));
        assert!(input.top[t.3].1<input.mid[t.0].1);
    }

    let heights=ans.iter().map(|&t|input.mid[t.0].2+input.low[t.1].2+input.low[t.2].2+input.top[t.3].2);
    let min=heights.clone().min().unwrap();
    let max=heights.max().unwrap();

    eprintln!("score = {}",40000-(max-min));
}



struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
impl Scanner{
    fn new()->Self{
        use std::io::Read;
        let mut tmp=String::new();
        std::io::stdin().read_to_string(&mut tmp).unwrap();
        Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}
    }

    fn read<T:std::str::FromStr>(&mut self)->T{
        self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))
    }
}



type Flow=usize;
const INF:Flow=Flow::MAX/4;



#[derive(Clone,Copy,Debug,Default)]
struct Edge{
    rev:usize,
    cap:Flow,
}



fn solve_dinic(g:&mut G<Edge>,s:usize,t:usize)->Flow{
    solve_dinic_with_capacity(g,s,t,INF)
}



fn solve_dinic_with_capacity(g:&mut G<Edge>,s:usize,t:usize,cap:Flow)->Flow{
    struct DFS{
        level:Vec<usize>,
        iter:Vec<usize>,
        que:Queue<usize>,
    }
    impl DFS{
        fn bfs(&mut self,g:&G<Edge>,s:usize,t:usize){
            self.level.fill(!0);
            self.level[s]=0;
            self.que.clear();
            self.que.push_back(s);
            while let Some(v)=self.que.pop_front(){
                for (nv,edge) in g.weight_iter(v){
                    if edge.cap==0 || self.level[nv]!=!0{
                        continue;
                    }
                    self.level[nv]=self.level[v]+1;
                    if nv==t{
                        return;
                    }
                    self.que.push_back(nv);
                }
            }
        }

        fn dfs(&mut self,g:&mut G<Edge>,s:usize,v:usize,add:Flow)->usize{
            if v==s{
                return add;
            }
            let mut res=0;
            let level0=self.level[v];
            while self.iter[v]<g[v].len(){
                let (nv,edge)=g[v][self.iter[v]];
                if level0<=self.level[nv] || g[nv][edge.rev].1.cap==0{
                    self.iter[v]+=1;
                    continue;
                }
                let d=self.dfs(g,s,nv,(add-res).min(g[nv][edge.rev].1.cap));
                if d==0{
                    self.iter[v]+=1;
                    continue;
                }

                g[v][self.iter[v]].1.cap+=d;
                g[nv][edge.rev].1.cap-=d;
                res+=d;
                self.iter[v]+=1;
                if res==add{
                    return res;
                }
            }

            self.level[v]=g.len();
            res
        }
    }

    let mut dfs=DFS{
        level:vec![0;g.len()],
        iter:vec![0;g.len()],
        que:Queue::new(),
    };

    let mut flow=0;
    while flow<cap{
        dfs.bfs(g,s,t);
        if dfs.level[t]==!0{
            break;
        }
        dfs.iter.fill(0);
        let add=dfs.dfs(g,s,t,cap-flow);
        if add==0{
            break;
        }
        flow+=add;
    }
    flow
}


fn restore_mincut(g:&G<Edge>,s:usize)->Vec<bool>{
    let mut seen=vec![false;g.len()];
    let mut que=Queue::new();
    que.push_back(s);
    seen[s]=true;
    while let Some(p)=que.pop_front(){
        for (nv,edge) in g.weight_iter(p){
            if edge.cap!=0 && !seen[nv]{
                seen[nv]=true;
                que.push_back(nv);
            }
        }
    }

    seen
}



struct MaxFlow{
    pos:Vec<(usize,usize)>,
    g:Vec<Vec<(usize,Edge)>>,
}
impl MaxFlow{
    fn new(n:usize)->Self{
        Self{
            pos:vec![],
            g:vec![vec![];n],
        }
    }

    fn add_edge(&mut self,s:usize,t:usize,cap:Flow)->usize{
        let id=self.pos.len();
        self.pos.push((s,self.g[s].len()));
        let from_id=self.g[s].len();
        let mut to_id=self.g[t].len();
        to_id+=(s==t) as usize;
        self.g[s].push((t,Edge{rev:to_id,cap}));
        self.g[t].push((s,Edge{rev:from_id,cap:0}));
        
        id
    }

    fn change_edge(&mut self,id:usize,new_flow:Flow,new_cap:Flow){
        assert!(new_flow<=new_cap);
        let e=&mut self.g[self.pos[id].0][self.pos[id].1];
        e.1.cap=new_cap-new_flow;
        let e=*e;
        self.g[e.0][e.1.rev].1.cap=new_flow;
    }

    fn get_cap(&self,id:usize)->Flow{
        let e=self.g[self.pos[id].0][self.pos[id].1];
        let re=self.g[e.0][e.1.rev];
        e.1.cap+re.1.cap
    }

    fn get_flow(&self,id:usize)->Flow{
        let e=self.g[self.pos[id].0][self.pos[id].1];
        let re=self.g[e.0][e.1.rev];
        re.1.cap
    }
    
    fn restore_mincut(&self,s:usize)->Vec<bool>{
        restore_mincut(&self.g,s)
    }

    fn solve(&mut self,s:usize,t:usize)->Flow{
        solve_dinic(&mut self.g,s,t)
    }

    fn solve_with_capacity(&mut self,s:usize,t:usize,cap:Flow)->Flow{
        solve_dinic_with_capacity(&mut self.g,s,t,cap)
    }
}





struct Queue<T>{
    data:Vec<T>,
    head:usize,
}
impl<T> Queue<T>{
    fn new()->Self{
        Queue{
            data:vec![],
            head:0,
        }
    }

    fn clear(&mut self){
        self.data.clear();
        self.head=0;
    }

    fn is_empty(&self)->bool{
        self.head==self.data.len()
    }

    fn len(&self)->usize{
        self.data.len()-self.head
    }

    fn push_back(&mut self,v:T){
        self.data.push(v);
    }

    fn pop_front(&mut self)->Option<T> where T:Copy{
        if self.head==self.data.len(){
            None
        } else{
            self.head+=1;
            Some(self.data[self.head-1])
        }
    }

    fn front(&self)->Option<&T>{
        if self.is_empty(){
            None
        } else{
            Some(&self.data[self.head])
        }
    }

    fn to_slice(&self)->&[T]{
        &self.data[self.head..]
    }
}
impl<T> std::ops::Deref for Queue<T>{
    type Target=[T];
    fn deref(&self)->&[T]{
        &self.data[self.head..]
    }
}
impl<T> std::ops::DerefMut for Queue<T>{
    fn deref_mut(&mut self)->&mut [T]{
        &mut self.data[self.head..]
    }
}
impl<T> std::ops::Index<usize> for Queue<T>{
    type Output=T;
    fn index(&self,n:usize)->&T{
        let idx=self.head+n;
        assert!(self.head<=idx);
        &self.data[idx]
    }
    
}
impl<T> std::ops::IndexMut<usize> for Queue<T>{
    fn index_mut(&mut self,n:usize)->&mut T{
        let idx=self.head+n;
        assert!(self.head<=idx);
        &mut self.data[idx]
    }
}





trait EdgeIter{
    type EdgeIter<'a>:Iterator<Item=usize> where Self:'a;
    fn edge_iter<'a>(&'a self,n:usize)->Self::EdgeIter<'a>;
}

trait WeightIter:EdgeIter{
    type T;
    type WeightIter<'a>:Iterator<Item=(usize,Self::T)> where Self:'a;
    fn weight_iter<'a>(&'a self,n:usize)->Self::WeightIter<'a>;
}

impl EdgeIter for Vec<Vec<usize>>{
    type EdgeIter<'a>=std::iter::Copied<std::slice::Iter<'a,usize>>;
    fn edge_iter<'a>(&'a self,n:usize)->Self::EdgeIter<'a>{
        self[n].iter().copied()
    }
}

impl<T> EdgeIter for Vec<Vec<(usize,T)>>{
    type EdgeIter<'a>=std::iter::Map<std::slice::Iter<'a,(usize,T)>,for<'b>fn(&'b(usize,T))->usize> where T:'a;
    fn edge_iter<'a>(&'a self,n:usize)->Self::EdgeIter<'a>{
        self[n].iter().map(|t|t.0)
    }
}

impl<T:Copy> WeightIter for Vec<Vec<(usize,T)>>{
    type T=T;
    type WeightIter<'a>=std::iter::Copied<std::slice::Iter<'a,(usize,T)>> where T: 'a;
    fn weight_iter<'a>(&'a self,n:usize)->Self::WeightIter<'a>{
        self[n].iter().copied()
    }
}

yukicoder

結果

コンパイルメッセージ

ソースコード