結果

問題 No.5007 Steiner Space Travel
ユーザー matsu7874
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

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], &centors[0]);
for j in 1..k {
let distance = dist_powered(&points[i], &centors[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);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0