結果

問題 No.1477 Lamps on Graph
ユーザー KFrom40KFrom40
提出日時 2021-04-16 22:43:43
言語 PHP
(8.3.4)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 1,949 bytes
コンパイル時間 737 ms
コンパイル使用メモリ 18,648 KB
実行使用メモリ 93,672 KB
最終ジャッジ日時 2023-09-16 01:48:00
合計ジャッジ時間 7,278 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
18,764 KB
testcase_01 AC 15 ms
18,884 KB
testcase_02 AC 16 ms
18,936 KB
testcase_03 AC 15 ms
18,956 KB
testcase_04 AC 15 ms
18,952 KB
testcase_05 AC 15 ms
18,740 KB
testcase_06 AC 15 ms
18,896 KB
testcase_07 AC 15 ms
18,924 KB
testcase_08 AC 15 ms
18,920 KB
testcase_09 AC 15 ms
18,964 KB
testcase_10 AC 15 ms
18,920 KB
testcase_11 AC 15 ms
18,980 KB
testcase_12 AC 149 ms
51,824 KB
testcase_13 AC 128 ms
47,396 KB
testcase_14 AC 179 ms
54,496 KB
testcase_15 AC 89 ms
33,256 KB
testcase_16 AC 50 ms
35,332 KB
testcase_17 AC 45 ms
28,968 KB
testcase_18 AC 95 ms
56,548 KB
testcase_19 AC 112 ms
45,448 KB
testcase_20 AC 58 ms
31,188 KB
testcase_21 AC 82 ms
53,748 KB
testcase_22 AC 50 ms
24,936 KB
testcase_23 AC 117 ms
37,864 KB
testcase_24 AC 186 ms
58,456 KB
testcase_25 AC 78 ms
31,208 KB
testcase_26 AC 155 ms
64,004 KB
testcase_27 AC 108 ms
37,356 KB
testcase_28 AC 104 ms
45,448 KB
testcase_29 AC 99 ms
39,372 KB
testcase_30 AC 46 ms
35,244 KB
testcase_31 AC 48 ms
35,208 KB
testcase_32 AC 170 ms
93,672 KB
testcase_33 AC 160 ms
82,628 KB
testcase_34 AC 130 ms
61,992 KB
testcase_35 AC 225 ms
78,180 KB
testcase_36 AC 227 ms
76,332 KB
testcase_37 AC 211 ms
72,192 KB
testcase_38 AC 224 ms
74,152 KB
testcase_39 AC 228 ms
76,264 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php
[$n,$m] = array_map('intval', explode(' ', trim(fgets(STDIN))));
//[$n] = array_map('intval', explode(' ', trim(fgets(STDIN))));
$a = array_map('intval', explode(' ', trim(fgets(STDIN))));
//[$s,$t] = explode(' ', trim(fgets(STDIN)));
//[$s] = explode(' ', trim(fgets(STDIN)));
//$s = explode(' ', trim(fgets(STDIN)));
//function decr($v){return --$v;}
//alpha='abcdefghijklmnopqrstuvwxyz';

$route = [];

$u = [];
$v = [];
for($i=0;$i<$m;$i++){
    [$u[],$v[]] = array_map('intval', explode(' ', trim(fgets(STDIN))));
}

[$k] = array_map('intval', explode(' ', trim(fgets(STDIN))));
$b = array_map('intval', explode(' ', trim(fgets(STDIN))));

$sw = array_fill(1, $n, false);
for($i=0;$i<$k;$i++){
    $sw[$b[$i]]=true;
}
$x = [];
for($i=0;$i<$n;$i++){
    $x[$i+1] = $a[$i];
}
$cnt = array_fill(1, $n, 0);
for($i=0;$i<$m;$i++){
    if($a[$u[$i]-1] < $a[$v[$i]-1]){
        if(!isset($route[$u[$i]])) $route[$u[$i]]=[];
        $route[$u[$i]][$v[$i]] = true;
        $cnt[$v[$i]]++;        
    }else if($a[$u[$i]-1] > $a[$v[$i]-1]){
        if(!isset($route[$v[$i]])) $route[$v[$i]]=[];
        $route[$v[$i]][$u[$i]] = true;
        $cnt[$u[$i]]++;        
    }
}
//var_dump($cnt);

$q = new SplQueue();
for($i=1;$i<=$n;$i++){
    if($cnt[$i]==0){
//        echo $i." ";
        $q->enqueue($i);
    }
}
//echo PHP_EOL;
$ans = 0;
$ans2 = [];
//echo "------------".PHP_EOL;
while($q->count() > 0){
    $i = $q->dequeue();
//    echo $i."=".($sw[$i] ? "on" : "off");
    if($sw[$i]) {
        $ans++;
        $ans2[] = $i;
    }
    if(!isset($route[$i])) {
//        echo PHP_EOL;
        continue;
    }
    foreach($route[$i] as $j => $v){
        $cnt[$j]--;
//        echo $j.":".$cnt[$j]." ";
        if($sw[$i]){
            $sw[$j] = !$sw[$j];
        }
        if($cnt[$j] == 0){
            $q->enqueue($j);
        }
    }
//    echo PHP_EOL;
}
//echo "------------".PHP_EOL;
echo $ans;
echo PHP_EOL;
echo implode(PHP_EOL, $ans2);
0