結果

問題 No.1477 Lamps on Graph
ユーザー KFrom40KFrom40
提出日時 2021-04-16 22:43:43
言語 PHP
(8.3.4)
結果
AC  
実行時間 245 ms / 2,000 ms
コード長 1,949 bytes
コンパイル時間 1,531 ms
コンパイル使用メモリ 30,916 KB
実行使用メモリ 74,800 KB
最終ジャッジ日時 2024-07-03 02:57:52
合計ジャッジ時間 8,635 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
31,392 KB
testcase_01 AC 41 ms
31,076 KB
testcase_02 AC 42 ms
30,876 KB
testcase_03 AC 41 ms
31,028 KB
testcase_04 AC 42 ms
31,008 KB
testcase_05 AC 41 ms
30,984 KB
testcase_06 AC 42 ms
30,888 KB
testcase_07 AC 42 ms
30,932 KB
testcase_08 AC 41 ms
30,792 KB
testcase_09 AC 41 ms
30,856 KB
testcase_10 AC 41 ms
31,356 KB
testcase_11 AC 41 ms
31,036 KB
testcase_12 AC 157 ms
54,072 KB
testcase_13 AC 133 ms
52,372 KB
testcase_14 AC 182 ms
56,392 KB
testcase_15 AC 104 ms
41,360 KB
testcase_16 AC 74 ms
40,532 KB
testcase_17 AC 71 ms
39,824 KB
testcase_18 AC 114 ms
52,068 KB
testcase_19 AC 127 ms
51,468 KB
testcase_20 AC 80 ms
37,968 KB
testcase_21 AC 103 ms
48,868 KB
testcase_22 AC 72 ms
34,956 KB
testcase_23 AC 129 ms
43,140 KB
testcase_24 AC 192 ms
61,000 KB
testcase_25 AC 98 ms
40,204 KB
testcase_26 AC 161 ms
60,516 KB
testcase_27 AC 117 ms
44,300 KB
testcase_28 AC 131 ms
50,316 KB
testcase_29 AC 121 ms
46,416 KB
testcase_30 AC 70 ms
40,312 KB
testcase_31 AC 71 ms
40,460 KB
testcase_32 AC 196 ms
74,800 KB
testcase_33 AC 185 ms
68,132 KB
testcase_34 AC 150 ms
52,436 KB
testcase_35 AC 245 ms
72,548 KB
testcase_36 AC 240 ms
71,992 KB
testcase_37 AC 228 ms
70,328 KB
testcase_38 AC 233 ms
70,376 KB
testcase_39 AC 238 ms
71,800 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