結果

問題 No.994 ばらばらコイン
ユーザー ynishi2015ynishi2015
提出日時 2020-02-21 21:52:19
言語 PHP
(8.3.4)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 3,248 bytes
コンパイル時間 2,656 ms
コンパイル使用メモリ 30,484 KB
実行使用メモリ 59,228 KB
最終ジャッジ日時 2024-04-17 07:35:06
合計ジャッジ時間 5,778 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
30,632 KB
testcase_01 AC 40 ms
30,640 KB
testcase_02 AC 116 ms
56,204 KB
testcase_03 AC 152 ms
59,228 KB
testcase_04 AC 149 ms
58,996 KB
testcase_05 AC 88 ms
44,940 KB
testcase_06 AC 151 ms
59,144 KB
testcase_07 AC 150 ms
58,600 KB
testcase_08 AC 114 ms
50,572 KB
testcase_09 AC 143 ms
58,140 KB
testcase_10 AC 112 ms
50,836 KB
testcase_11 AC 124 ms
53,664 KB
testcase_12 AC 129 ms
55,312 KB
testcase_13 AC 40 ms
30,700 KB
testcase_14 AC 40 ms
31,144 KB
testcase_15 AC 40 ms
31,056 KB
testcase_16 AC 40 ms
30,964 KB
testcase_17 AC 40 ms
31,088 KB
testcase_18 AC 40 ms
30,700 KB
testcase_19 AC 40 ms
30,908 KB
testcase_20 AC 40 ms
31,020 KB
testcase_21 AC 40 ms
30,956 KB
testcase_22 AC 41 ms
30,908 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php
list($n, $k) = ints();
$K = $k;
$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,"\n";
}else{
    echo $K-1;
}
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