結果
| 問題 | No.1639 最小通信路 |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2021-08-06 21:59:56 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,346 bytes |
| コンパイル時間 | 14,533 ms |
| コンパイル使用メモリ | 383,072 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-09-17 01:57:22 |
| 合計ジャッジ時間 | 15,637 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
コンパイルメッセージ
warning: unnecessary parentheses around type
--> src/main.rs:119:15
|
119 | fn readi() -> (i64) {
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
119 - fn readi() -> (i64) {
119 + fn readi() -> i64 {
|
warning: unused variable: `x`
--> src/main.rs:330:17
|
330 | let mut x = 0 as usize;
| ^ help: if this is intentional, prefix it with an underscore: `_x`
|
= note: `#[warn(unused_variables)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:330:13
|
330 | let mut x = 0 as usize;
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:333:17
|
333 | let mut e = Edge {
| ----^
| |
| help: remove this `mut`
warning: unused variable: `i`
--> src/main.rs:381:9
|
381 | for i in 0..n * (n - 1) / 2 {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
warning: variable does not need to be mutable
--> src/main.rs:387:13
|
387 | let mut c: f64 = s.next().unwrap().parse().unwrap();
| ----^
| |
| help: remove this `mut`
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::fmt::Debug;
use std::fs::File;
use std::io::prelude::*;
use std::io::*;
use std::marker::Copy;
use std::mem::*;
use std::ops::Bound::*;
use std::ops::{Add, Mul, Neg, Sub};
use std::str;
use std::vec;
use std::{cmp, process::Output};
use std::{cmp::Ordering, env::consts::DLL_PREFIX};
use std::{cmp::Ordering::*, f32::consts::PI};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const FINF: f64 = 122337203685.0;
const INF128: i128 = 1223372036854775807000000000000;
const LINF: i64 = 2147483647;
const MOD: i64 = 1000000007;
// const MOD: i64 = 998244353;
const T: bool = true;
const F: bool = false;
const MPI: f64 = 3.14159265358979323846264338327950288f64;
// const MOD: i64 = INF;
const UMOD: usize = MOD as usize;
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
use crate::kraskal::kraskal;
macro_rules! p {
($x:expr) => {
println!("{}", $x);
};
}
macro_rules! d {
($x:expr) => {
println!("{:?}", $x);
};
}
macro_rules! dd {
(x:expr) => {
dbg!(x);
};
}
macro_rules! chmin {
($base:expr, $($cmps:expr),+ $(,)*) => {{
let cmp_min = min!($($cmps),+);
if $base > cmp_min {
$base = cmp_min;
true
} else {
false
}
}};
}
macro_rules! chmax {
($base:expr, $($cmps:expr),+ $(,)*) => {{
let cmp_max = max!($($cmps),+);
if $base < cmp_max {
$base = cmp_max;
true
} else {
false
}
}};
}
macro_rules! min {
($a:expr $(,)*) => {{
$a
}};
($a:expr, $b:expr $(,)*) => {{
std::cmp::min($a, $b)
}};
($a:expr, $($rest:expr),+ $(,)*) => {{
std::cmp::min($a, min!($($rest),+))
}};
}
macro_rules! max {
($a:expr $(,)*) => {{
$a
}};
($a:expr, $b:expr $(,)*) => {{
std::cmp::max($a, $b)
}};
($a:expr, $($rest:expr),+ $(,)*) => {{
std::cmp::max($a, max!($($rest),+))
}};
}
// use str::Chars;
// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn readi() -> (i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
iter.next().unwrap().parse::<i64>().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
fn readff() -> (f64, f64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<f64>().unwrap(),
iter.next().unwrap().parse::<f64>().unwrap(),
)
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readcc() -> (char, char) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<char>().unwrap(),
iter.next().unwrap().parse::<char>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuu() -> (usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readiiii() -> (i64, i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[derive(PartialEq, PartialOrd, Clone, Copy)]
pub struct F64Total(f64);
impl Eq for F64Total {}
impl Ord for F64Total {
fn cmp(&self, other: &F64Total) -> Ordering {
let F64Total(f1) = *self;
let F64Total(f2) = *other;
if f1.is_nan() {
Less
} else if f2.is_nan() {
Greater
} else {
if (f1 - f2).is_sign_positive() {
Greater
} else {
Less
}
}
}
}
pub struct Dsu {
n: usize,
// root node: -1 * component size
// otherwise: parent
parent_or_size: Vec<i32>,
}
impl Dsu {
// 0 <= size <= 10^8 is constrained.
pub fn new(size: usize) -> Self {
Self {
n: size,
parent_or_size: vec![-1; size],
}
}
pub fn merge(&mut self, a: usize, b: usize) -> usize {
assert!(a < self.n);
assert!(b < self.n);
let (mut x, mut y) = (self.leader(a), self.leader(b));
if x == y {
return x;
}
if -self.parent_or_size[x] < -self.parent_or_size[y] {
std::mem::swap(&mut x, &mut y);
}
self.parent_or_size[x] += self.parent_or_size[y];
self.parent_or_size[y] = x as i32;
x
}
pub fn same(&mut self, a: usize, b: usize) -> bool {
assert!(a < self.n);
assert!(b < self.n);
self.leader(a) == self.leader(b)
}
pub fn leader(&mut self, a: usize) -> usize {
assert!(a < self.n);
if self.parent_or_size[a] < 0 {
return a;
}
self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;
self.parent_or_size[a] as usize
}
pub fn size(&mut self, a: usize) -> usize {
assert!(a < self.n);
let x = self.leader(a);
-self.parent_or_size[x] as usize
}
pub fn groups(&mut self) -> Vec<Vec<usize>> {
let mut leader_buf = vec![0; self.n];
let mut group_size = vec![0; self.n];
for i in 0..self.n {
leader_buf[i] = self.leader(i);
group_size[leader_buf[i]] += 1;
}
let mut result = vec![Vec::new(); self.n];
for i in 0..self.n {
result[i].reserve(group_size[i]);
}
for i in 0..self.n {
result[leader_buf[i]].push(i);
}
result
.into_iter()
.filter(|x| !x.is_empty())
.collect::<Vec<Vec<usize>>>()
}
}
mod kraskal {
use crate::Dsu;
use crate::F64Total;
pub struct Edge {
pub u: usize,
pub v: usize,
pub cost: F64Total,
}
#[doc = "es: undirected edges. O(ElogV)"]
pub fn kraskal(n: usize, ess: Vec<(usize, usize, F64Total)>) -> (Vec<Edge>, Vec<Edge>) {
let mut used = vec![];
let mut unused = vec![];
let mut x = 0 as usize;
let mut es = vec![];
for i in 0..ess.len() {
let mut e = Edge {
u: ess[i].0,
v: ess[i].1,
cost: ess[i].2,
};
es.push(e);
}
es.sort_by_key(|x| x.cost);
let mut uf = Dsu::new(n);
for e in es {
if !uf.same(e.u, e.v) {
uf.merge(e.u, e.v);
used.push(e);
} else {
unused.push(e);
}
}
(used, unused)
}
pub fn kraskal_es(n: usize, es: Vec<Edge>) -> (Vec<Edge>, Vec<Edge>) {
let mut used = vec![];
let mut unused = vec![];
let mut es = es;
es.sort_by_key(|x| x.cost);
let mut uf = Dsu::new(n);
for e in es {
if !uf.same(e.u, e.v) {
uf.merge(e.u, e.v);
used.push(e);
} else {
unused.push(e);
}
}
(used, unused)
}
}
fn solve() {
let n: usize = read();
let mut vp = vec![];
for i in 0..n * (n - 1) / 2 {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let mut s = s.split_whitespace();
let mut x: usize = s.next().unwrap().parse().unwrap();
let mut y: usize = s.next().unwrap().parse().unwrap();
let mut c: f64 = s.next().unwrap().parse().unwrap();
x -= 1;
y -= 1;
let c = F64Total(c);
vp.push((x, y, c));
}
let r = kraskal(n, vp);
let mut res = 0.0;
for i in 0..(r.0).len() {
if (r.0)[i].cost.0 > res {
res = (r.0)[i].cost.0
}
}
println!("{:?}", res);
return;
}
fn main() {
solve();
}