結果

問題 No.1477 Lamps on Graph
ユーザー KFrom40KFrom40
提出日時 2021-04-16 22:43:43
言語 PHP
(843.2)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
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