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

提出ソース

結果

問題	No.2596 Christmas Eve (Heuristic ver.)
ユーザー	rhoo
提出日時	2023-11-27 21:07:31
言語	Rust (1.77.0)
結果	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
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	48 ms 37,056 KB
testcase_01	AC	51 ms 38,812 KB
testcase_02	AC	50 ms 37,500 KB
testcase_03	AC	48 ms 36,960 KB
testcase_04	AC	47 ms 37,752 KB
testcase_05	AC	50 ms 38,440 KB
testcase_06	AC	45 ms 34,560 KB
testcase_07	AC	47 ms 37,540 KB
testcase_08	AC	48 ms 38,228 KB
testcase_09	AC	48 ms 37,804 KB
testcase_10	AC	49 ms 38,132 KB
testcase_11	AC	49 ms 38,320 KB
testcase_12	AC	50 ms 38,324 KB
testcase_13	AC	51 ms 38,416 KB
testcase_14	AC	46 ms 37,096 KB
testcase_15	AC	45 ms 36,448 KB
testcase_16	AC	50 ms 38,480 KB
testcase_17	AC	48 ms 38,064 KB
testcase_18	AC	48 ms 38,120 KB
testcase_19	AC	52 ms 37,520 KB
testcase_20	AC	45 ms 37,096 KB
testcase_21	AC	50 ms 37,988 KB
testcase_22	AC	47 ms 37,476 KB
testcase_23	AC	50 ms 38,416 KB
testcase_24	AC	48 ms 37,588 KB
testcase_25	AC	52 ms 38,844 KB
testcase_26	AC	47 ms 37,204 KB
testcase_27	AC	47 ms 37,128 KB
testcase_28	AC	48 ms 38,604 KB
testcase_29	AC	45 ms 36,916 KB
testcase_30	AC	49 ms 37,948 KB
testcase_31	AC	48 ms 36,656 KB
testcase_32	AC	54 ms 38,464 KB
testcase_33	AC	46 ms 37,144 KB
testcase_34	AC	47 ms 37,708 KB
testcase_35	AC	46 ms 36,620 KB
testcase_36	AC	46 ms 34,688 KB
testcase_37	AC	48 ms 38,144 KB
testcase_38	AC	48 ms 36,952 KB
testcase_39	AC	49 ms 38,272 KB
testcase_40	AC	48 ms 37,908 KB
testcase_41	AC	48 ms 37,820 KB
testcase_42	AC	50 ms 38,596 KB
testcase_43	AC	44 ms 34,176 KB
testcase_44	AC	50 ms 38,128 KB
testcase_45	AC	45 ms 36,896 KB
testcase_46	AC	48 ms 38,224 KB
testcase_47	AC	45 ms 34,432 KB
testcase_48	AC	50 ms 38,788 KB
testcase_49	AC	49 ms 38,708 KB
testcase_50	AC	45 ms 36,992 KB
testcase_51	AC	49 ms 37,888 KB
testcase_52	AC	49 ms 37,756 KB
testcase_53	AC	49 ms 37,832 KB
testcase_54	AC	50 ms 38,640 KB
testcase_55	AC	50 ms 37,860 KB
testcase_56	AC	50 ms 38,712 KB
testcase_57	AC	50 ms 38,384 KB
testcase_58	AC	47 ms 37,920 KB
testcase_59	AC	46 ms 36,864 KB
testcase_60	AC	50 ms 38,404 KB
testcase_61	AC	51 ms 38,692 KB
testcase_62	AC	49 ms 37,416 KB
testcase_63	AC	50 ms 38,340 KB
testcase_64	AC	49 ms 38,084 KB
testcase_65	AC	46 ms 37,604 KB
testcase_66	AC	47 ms 38,160 KB
testcase_67	AC	47 ms 37,200 KB
testcase_68	AC	49 ms 38,216 KB
testcase_69	AC	46 ms 37,808 KB
testcase_70	AC	46 ms 37,216 KB
testcase_71	AC	46 ms 37,200 KB
testcase_72	AC	49 ms 38,140 KB
testcase_73	AC	48 ms 38,504 KB
testcase_74	AC	47 ms 36,832 KB
testcase_75	AC	48 ms 37,352 KB
testcase_76	AC	51 ms 38,940 KB
testcase_77	AC	50 ms 38,188 KB
testcase_78	AC	47 ms 36,932 KB
testcase_79	AC	50 ms 38,960 KB
testcase_80	AC	51 ms 38,844 KB
testcase_81	AC	44 ms 34,688 KB
testcase_82	AC	50 ms 38,784 KB
testcase_83	AC	49 ms 38,500 KB
testcase_84	AC	47 ms 37,292 KB
testcase_85	AC	45 ms 37,152 KB
testcase_86	AC	46 ms 37,304 KB
testcase_87	AC	48 ms 37,924 KB
testcase_88	AC	48 ms 37,940 KB
testcase_89	AC	48 ms 37,572 KB
testcase_90	AC	44 ms 36,840 KB
testcase_91	AC	47 ms 38,432 KB
testcase_92	AC	47 ms 38,736 KB
testcase_93	AC	47 ms 38,292 KB
testcase_94	AC	48 ms 38,312 KB
testcase_95	AC	47 ms 37,344 KB
testcase_96	AC	50 ms 38,956 KB
testcase_97	AC	48 ms 37,720 KB
testcase_98	AC	47 ms 37,712 KB
testcase_99	AC	49 ms 38,172 KB
testcase_100	AC	50 ms 38,928 KB
testcase_101	AC	48 ms 38,168 KB
testcase_102	AC	48 ms 37,324 KB
testcase_103	AC	48 ms 37,264 KB
testcase_104	AC	48 ms 38,300 KB
testcase_105	AC	49 ms 37,896 KB
testcase_106	AC	52 ms 38,444 KB
testcase_107	AC	48 ms 38,436 KB
testcase_108	AC	50 ms 38,632 KB
testcase_109	AC	48 ms 37,428 KB
testcase_110	AC	47 ms 37,620 KB
testcase_111	AC	45 ms 36,740 KB
testcase_112	AC	48 ms 38,728 KB
testcase_113	AC	47 ms 36,712 KB
testcase_114	AC	48 ms 37,812 KB
testcase_115	AC	49 ms 38,224 KB
testcase_116	AC	50 ms 38,744 KB
testcase_117	AC	49 ms 38,356 KB
testcase_118	AC	48 ms 37,748 KB
testcase_119	AC	49 ms 38,476 KB
testcase_120	AC	48 ms 38,204 KB
testcase_121	AC	52 ms 38,376 KB
testcase_122	AC	51 ms 38,540 KB
testcase_123	AC	47 ms 37,384 KB
testcase_124	AC	50 ms 38,176 KB

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

コンパイルメッセージ

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

結果

テストケース

コンパイルメッセージ

ソースコード