結果

問題 No.1477 Lamps on Graph
ユーザー KFrom40
提出日時 2021-04-16 21:53:58
言語 PHP
(843.2)
結果
WA  
実行時間 -
コード長 1,599 bytes
コンパイル時間 3,647 ms
コンパイル使用メモリ 30,568 KB
実行使用メモリ 87,216 KB
最終ジャッジ日時 2024-07-03 01:35:01
合計ジャッジ時間 14,236 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
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($u < $v){
        if(!isset($route[$u[$i]])) $route[$u[$i]]=[];
        $route[$u[$i]][$v[$i]] = true;
        $cnt[$v[$i]]++;        
    }else{
        if(!isset($route[$v[$i]])) $route[$v[$i]]=[];
        $route[$v[$i]][$u[$i]] = true;
        $cnt[$u[$i]]++;        
    }
}

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