結果
| 問題 | No.1094 木登り / Climbing tree |
| ユーザー |
 uw_yu1rabbit
|
| 提出日時 | 2021-02-08 17:57:05 |
| 言語 | Rust (1.77.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 3,734 bytes |
| コンパイル時間 | 1,544 ms |
| コンパイル使用メモリ | 154,080 KB |
| 実行使用メモリ | 102,144 KB |
| 最終ジャッジ日時 | 2023-09-19 07:47:31 |
| 合計ジャッジ時間 | 16,148 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
コンパイルメッセージ
warning: variable does not need to be mutable
--> Main.rs:15:13
|
15 | let mut dep:Vec<i32> = vec![0;_n];
| ----^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> Main.rs:16:13
|
16 | let mut c:Vec<i32> = vec![0;_n];
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:17:13
|
17 | let mut C:Vec<Vec<i32>> = vec![vec![];_n];
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:19:13
|
19 | let mut digit:usize = 64;
| ----^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:20:13
|
20 | let mut doub:Vec<Vec<i32>> = vec![vec![-1;_n];digit];
| ----^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:85:13
|
85 | let mut f = self.answer_to_query(u,v) as usize;
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:90:13
|
90 | let mut f = self.answer_to_query(u,v) as usize;
| ----^
| |
| help: remove this `mut`
warning: field `n` is never read
--> Main.rs:8:5
|
3 | struct LCA{
| --- field in this struct
...
8 | n:usize,
| ^
|
= note: `#[warn(dead_code)]` on by default
warning: associated function `length` is never used
--> Main.rs:84:8
|
84 | fn length(&mut self,u:usize,v:usize) -> i32 {
| ^^^^^^
warning: associated function `is_on_path` is never used
--> Main.rs:94:8
|
94 | fn is_on_path(&mut self,u:usize,v:usize,x:usize)
ソースコード
use std::io::*;
use std::str::FromStr;
struct LCA{
depth:Vec<i32>,
dig:i32,
cost:Vec<Vec<i32>>,
costs:Vec<i32>,
n:usize,
g:Vec<Vec<i32>>,
doubling:Vec<Vec<i32>>
}
impl LCA{
fn new(_n:usize) -> Self{
let mut dep:Vec<i32> = vec![0;_n];
let mut c:Vec<i32> = vec![0;_n];
let mut C:Vec<Vec<i32>> = vec![vec![];_n];
let mut _g:Vec<Vec<i32>> = vec![vec![];_n];
let mut digit:usize = 64;
let mut doub:Vec<Vec<i32>> = vec![vec![-1;_n];digit];
LCA{
depth:dep,
costs:c,
cost:C,
doubling:doub,
n:_n,
dig:digit as i32,
g:_g
}
}
fn addedge(&mut self,u:usize,v:usize,c:i32){//コスト指定がなければc = 0を渡す
self.g[u].push(v as i32);
self.g[v].push(u as i32);
self.cost[u].push(c);
self.cost[v].push(c);
}
fn dfs(&mut self,now:usize,par:i32,d:i32,c:i32){
self.doubling[0][now] = par;
self.depth[now] = d;
self.costs[now] = c;
for i in 0..self.g[now].len(){
if self.g[now][i] != par {
self.dfs(self.g[now][i] as usize,now as i32,d + 1, c + self.cost[now][i]);
}
}
}
fn construct(&mut self){
self.dfs(0,-1,0,0);
for i in 0..(self.dig as usize - 1){
for j in 0..self.doubling[i].len(){
if self.doubling[i][j] == -1{
self.doubling[i + 1][j] = -1;
} else {
self.doubling[i + 1][j] = self.doubling[i][self.doubling[i][j] as usize];
}
}
}
}
fn answer_to_query(&mut self, mut u:usize,mut v:usize) -> i32{
if self.depth[u] > self.depth[v] {
std::mem::swap(&mut u,&mut v);
}
for i in (0..self.dig as usize).rev(){
if ((self.depth[v] - self.depth[u]) >> i) & 1 == 0{
v = self.doubling[i][v] as usize;
}
}
if u == v {
return u as i32;
}
for i in (0..self.dig as usize).rev(){
if self.doubling[i][u] != self.doubling[i][v]{
u = self.doubling[i][u] as usize;
v = self.doubling[i][v] as usize;
}
}
self.doubling[0][u]
}
fn length(&mut self,u:usize,v:usize) -> i32 {
let mut f = self.answer_to_query(u,v) as usize;
self.depth[u] + self.depth[v] - 2 * self.depth[f]
}
fn dist(&mut self, u:usize,v:usize)-> i32 {
let mut f = self.answer_to_query(u,v) as usize;
self.costs[u] + self.costs[v] - 2 * self.costs[f]
}
fn is_on_path(&mut self,u:usize,v:usize,x:usize) -> bool {
self.length(u,x) + self.length(v,x) == self.length(u,v)
}
}
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn main(){
let n:usize = read();
let mut abc:Vec<Vec<i32>> = vec![vec![0;3];n];
let mut lca = LCA::new(n);
for i in 0..n - 1{
abc[i] = (0..3).map(|_| read()).collect();
lca.addedge(abc[i][0] as usize - 1, abc[i][1] as usize - 1, abc[i][2]);
}
lca.construct();
let q:usize = read();
let mut _q:Vec<Vec<usize>> = vec![vec![0;2];q];
for i in 0..q{
_q[i] = (0..2).map(|_| read()).collect();
}
for i in 0..q{
println!("{}",lca.dist(_q[i][0] - 1,_q[i][1] - 1));
}
}