結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 16:38:15 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 5,530 bytes |
コンパイル時間 | 1,128 ms |
実行使用メモリ | 5,160 KB |
スコア | 4,521,707 |
最終ジャッジ日時 | 2022-07-30 16:38:19 |
合計ジャッジ時間 | 2,605 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
コンパイルメッセージ
warning: value assigned to `t` is never read --> Main.rs:7:17 | 7 | let mut t = 0; | ^ | = note: `#[warn(unused_assignments)]` on by default = help: maybe it is overwritten before being read? warning: unused variable: `cluster_ids` --> Main.rs:129:5 | 129 | cluster_ids: &[usize], | ^^^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_cluster_ids` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `n` --> Main.rs:171:10 | 171 | let (n, m, planets) = read_input(); | ^ help: if this is intentional, prefix it with an underscore: `_n` warning: constant is never used: `STATION` --> Main.rs:125:1 | 125 | const STATION: usize = 2; | ^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: 4 warnings emitted
ソースコード
static mut XORSHIFT1: u128 = 123456789;static mut XORSHIFT2: u128 = 362436069;static mut XORSHIFT3: u128 = 521288629;static mut XORSHIFT4: u128 = 88675123;fn xorshift() -> u128 {unsafe {let mut t = 0;t = XORSHIFT1 ^ (XORSHIFT1 << 11u128);XORSHIFT1 = XORSHIFT2;XORSHIFT2 = XORSHIFT3;XORSHIFT3 = XORSHIFT4;XORSHIFT4 = (XORSHIFT4 ^ (XORSHIFT4 >> 19u128)) ^ (t ^ (t >> 8u128));t}}fn read_input() -> (usize, usize, Vec<(i32, i32)>) {let (n, m) = {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let s = s.trim_end().to_owned();let mut ws = s.split_whitespace();let n: usize = ws.next().unwrap().parse().unwrap();let m: usize = ws.next().unwrap().parse().unwrap();(n, m)};let mut xy = vec![];for _ in 0..n {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let s = s.trim_end().to_owned();let mut ws = s.split_whitespace();let a: i32 = ws.next().unwrap().parse().unwrap();let b: i32 = ws.next().unwrap().parse().unwrap();xy.push((a, b));}(n, m, xy)}const MAX_X: i32 = 1000;type Point = (i32, i32);// fn dist(p: &Point, q: &Point) -> i32 {// (((p.0 - q.0) * (p.0 - q.0) + (p.1 - q.1) * (p.1 - q.1)) as f64).sqrt() as i32// }fn dist_powered(p: &Point, q: &Point) -> i32 {(p.0 - q.0) * (p.0 - q.0) + (p.1 - q.1) * (p.1 - q.1)}fn kmeans(points: &[Point], k: usize, max_iter: usize) -> (Vec<Point>, Vec<usize>) {let n = points.len();let mut centors = vec![((xorshift() as i32).abs() % (MAX_X + 1),(xorshift() as i32).abs() % (MAX_X + 1),);k];let mut cluster_ids = vec![0; n];let mut cluster_sizes = vec![0; k];cluster_sizes[0] = n as i32;let mut updated = false;for _ in 0..max_iter {// 各点から最も近い代表点を探すfor i in 0..n {let mut nearest_centor_id = 0;let mut nearest_centor_distance = dist_powered(&points[i], ¢ors[0]);for j in 1..k {let distance = dist_powered(&points[i], ¢ors[j]);if distance < nearest_centor_distance {nearest_centor_distance = distance;nearest_centor_id = j;}}if nearest_centor_id != cluster_ids[i] {cluster_sizes[cluster_ids[i]] -=1;cluster_ids[i] = nearest_centor_id;cluster_ids[nearest_centor_id] += 1;updated = true;}}// 代表点の座標をクラスタの中心に移動するlet mut dxs = vec![0; k];let mut dys = vec![0; k];for i in 0..n {let cid = cluster_ids[i];dxs[cid] += points[i].0 - centors[cid].0;dys[cid] += points[i].1 - centors[cid].1;}for i in 0..k {if cluster_sizes[i] == 0{continue;}centors[i].0 += dxs[i]/cluster_sizes[i];centors[i].1 += dys[i]/cluster_sizes[i];}if !updated {break;}}(centors, cluster_ids)}// fn tsp_dp(points:&[Point])->Vec<usize>{// let n = points.len();// let mut dp = vec![]// }const ALPHA: i32 = 5;fn get_cost_coefficient(t1: usize, t2: usize) -> i32 {if t1 == PLANET {if t2 == PLANET {ALPHA * ALPHA} else {ALPHA}} else {if t2 == PLANET {ALPHA} else {1}}}const PLANET: usize = 1;const STATION: usize = 2;fn search_path(stations: &[Point],planets: &[Point],cluster_ids: &[usize],) -> Vec<(usize, usize)> {let mut path = vec![(PLANET, 0)];let mut visited = vec![false; planets.len()];visited[0] = true;let mut count_visited_planets = 1;let mut cur_type = PLANET;let mut cur_point = planets[0];while count_visited_planets < planets.len() {// まだ到達していない惑星のなかで距離が最小のものに移動するlet mut nearest_distance = i32::MAX;let mut nearest_id = (PLANET, 0);for i in 0..planets.len() {if visited[i] {continue;}let distance = get_cost_coefficient(cur_type, PLANET) * dist_powered(&cur_point, &planets[i]);if distance < nearest_distance {nearest_distance = distance;nearest_id = (PLANET, i);}}if nearest_id.0 == PLANET {count_visited_planets += 1;visited[nearest_id.1] = true;}cur_type = nearest_id.0;cur_point = if nearest_id.0 == PLANET {planets[nearest_id.1]} else {stations[nearest_id.1]};path.push((cur_type, nearest_id.1));}path.push((PLANET, 0));path}fn main() {let (n, m, planets) = read_input();let (stations, cluster_ids) = kmeans(&planets, m, 100);let path = search_path(&stations, &planets, &cluster_ids);assert!(path.len() <= 100000);for (x, y) in stations.iter() {println!("{} {}", x, y);}println!("{}", path.len());for (t, i) in path.iter() {println!("{} {}", t, i + 1);}}