結果

問題 No.994 ばらばらコイン
コンテスト
ユーザー ynishi2015
提出日時 2020-02-21 21:44:08
言語 PHP
(843.2)
結果
WA  
実行時間 -
コード長 3,235 bytes
コンパイル時間 1,297 ms
コンパイル使用メモリ 32,404 KB
実行使用メモリ 61,300 KB
最終ジャッジ日時 2024-10-08 21:30:08
合計ジャッジ時間 4,071 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php
list($n, $k) = ints();

$distance = array_fill(1, $n, PHP_INT_MAX);
for($i = 0; $i < $n-1; $i++){
    list($f, $t) = ints();
    $G[$f][] = $t;
    $G[$t][] = $f;
}
$current = [1];
$distance[1] = 0;
$d = 0;
while($current){
    $d++;
    $next = [];
    foreach($current as $c){
        foreach($G[$c] as $n){
            if($distance[$n] == PHP_INT_MAX){
                $distance[$n] = $d;
                $next[] = $n;
            }
        }
    }
    $current = $next;
}
$count = array_fill(0,$n+1, 0);
foreach($distance as $d){
    if($d != PHP_INT_MAX)$count[$d]++;
}
$ans = 0;
foreach($count as $dist => $count){
    if($dist < PHP_INT_MAX){
        for($i = 0; $i < $count; $i++){
            if($k == 0)break 2;
            $k--;
            $ans+=$dist;
        }
    }
}
if($k > 0){
    echo -1;
}else{
    echo $ans;
}
exit;
o($count);
o($G);

function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array: ";
            echo implode(" ", addIndex($val))."\n";
        }else{
            echo "array:array\n";
            if(isCleanArray($val)){
                foreach($val as $row)echo implode(" ", addIndex($row))."\n";
            }else{
                foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row))."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}
function addIndex($val){
    if(!isCleanArray($val)){
        $val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);
    }
    return $val;
}
function isCleanArray($array){
    $clean = true;
    $i = 0;
    foreach($array as $k => $v){
        if($k != $i++)$clean = false;
    }
    return $clean;
}
/**
 * 座圧対象の配列を渡すと以下の値を返す
 * ・圧縮された配列
 * ・復元用のMap
 * ・圧縮用のMap
 **/
function atsu($array){
    $a = array_flip($array);
    $fuku = array_flip($a);
    sort($fuku);
    $atsu = array_flip($fuku);
    foreach($array as $i => $val)$array[$i] = $atsu[$val];
    return [$array, $fuku, $atsu];
}
//配列の最大公約数
function gcdAll($array){
    $gcd = $array[0];
    for($i = 1; $i < count($array); $i++){
        $gcd = gcd($gcd, $array[$i]);
    }
    return $gcd;
}

//最大公約数
function gcd($m, $n){
    if(!$n)return $m;
    return gcd($n, $m % $n);
}

//配列の最小公倍数
function lcmAll($array){
    $lcm = $array[0];
    for($i = 1; $i < count($array); $i++){
        $lcm = lcm($lcm, $array[$i]);
    }
    return $lcm;
}

//最小公倍数
function lcm($a, $b) {
    return $a / gcd($a, $b) * $b;
}
//ビットカウント-1の数を数える
function popcount($x){
    $con = 0;
    while ($x) {
        $x &= $x-1;
        ++$con;
    }
    return $con;
}
0