結果

問題 No.5023 Airlines Optimization
コンテスト
ユーザー ikoma
提出日時 2026-02-28 15:50:35
言語 Rust
(1.93.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 2,605 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,597 ms
コンパイル使用メモリ 208,180 KB
実行使用メモリ 7,844 KB
スコア 36,438,156
最終ジャッジ日時 2026-02-28 15:50:56
合計ジャッジ時間 10,115 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;

#[derive(Clone, Copy)]
struct City {
    x: i32,
    y: i32,
    w: i64,
}

#[derive(Clone, Copy)]
struct Flight {
    a: usize,
    s: i32,
    b: usize,
    t: i32,
}

const START_MIN: i32 = 6 * 60;
const END_MIN: i32 = 21 * 60;

fn parse_time(s: &str) -> i32 {
    let hh: i32 = s[0..2].parse().unwrap();
    let mm: i32 = s[3..5].parse().unwrap();
    hh * 60 + mm
}

fn format_time(m: i32) -> String {
    let hh = m / 60;
    let mm = m % 60;
    format!("{:02}:{:02}", hh, mm)
}

fn ceil_to_5(x: f64) -> i32 {
    ((x / 5.0).ceil() as i32) * 5
}

fn flight_duration(c1: City, c2: City) -> i32 {
    let dx = (c1.x - c2.x) as f64;
    let dy = (c1.y - c2.y) as f64;
    let d = (dx * dx + dy * dy).sqrt();
    let mins = 60.0 * d / 800.0 + 40.0;
    ceil_to_5(mins)
}

fn next_departure(cur: i32, step: i32) -> i32 {
    ((cur + step - 1) / step) * step
}

fn main() {
    input! {
        n: usize,
        _r: i32,
    }
    let mut cities = Vec::with_capacity(n);
    for _ in 0..n {
        input! { x: i32, y: i32, w: i64 }
        cities.push(City { x, y, w });
    }

    input! { m: usize }
    for _ in 0..m {
        input! {
            _a: usize,
            s: String,
            _b: usize,
            _t: String,
        }
        let _ = parse_time(&s);
    }

    input! { k: usize }

    let mut order: Vec<usize> = (0..n).collect();
    order.sort_by_key(|&i| std::cmp::Reverse(cities[i].w));

    let hub = order[0] + 1;
    let mut routes: Vec<Vec<Flight>> = vec![Vec::new(); k];

    for plane in 0..k {
        if n <= 1 {
            break;
        }

        let target_idx = 1 + (plane % (n - 1));
        let target = order[target_idx] + 1;

        let mut cur_city = hub;
        let mut cur_time = START_MIN;

        loop {
            let next_city = if cur_city == hub { target } else { hub };
            let dur = flight_duration(cities[cur_city - 1], cities[next_city - 1]);
            let dep = next_departure(cur_time, 5);
            let arr = dep + dur;
            if arr > END_MIN {
                break;
            }
            routes[plane].push(Flight {
                a: cur_city,
                s: dep,
                b: next_city,
                t: arr,
            });
            cur_city = next_city;
            cur_time = arr;
        }
    }

    for r in routes {
        println!("{}", r.len());
        for f in r {
            println!(
                "{} {} {} {}",
                f.a,
                format_time(f.s),
                f.b,
                format_time(f.t)
            );
        }
    }
}
0