結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:55:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 219 ms / 2,000 ms |
コード長 | 1,179 bytes |
コンパイル時間 | 2,276 ms |
コンパイル使用メモリ | 202,844 KB |
最終ジャッジ日時 | 2025-01-20 19:08:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for (int i=0; i < (n); i++)using namespace std;using ll = long long;int main(){ios::sync_with_stdio(false);int N,M; cin>>N>>M;vector<int> A(N+1,0);vector<int> light(N+1,0);rep(i,N){int a;cin>>a; A[i+1] = -a;}vector<vector<int>> load(N+1,vector<int>());rep(i,M){int u,v; cin>>u>>v;load[u].push_back(v);load[v].push_back(u);}priority_queue<pair<int,int>> que; //強さ・番号int K; cin>>K;rep(i,K){int B; cin>>B;light[B]=1;que.push(make_pair(A[B],B));}vector<int> ans;while(que.size()){auto x = que.top(); que.pop();int a = x.first, b=x.second;if(light[b]==0) continue;light[b]=0;// cerr << a << " " << b <<endl;ans.push_back(b);for(int s:load[b]){if(A[s]<a){light[s] = (light[s]+1)%2;}if(light[s]){que.push(make_pair(A[s],s));}}}cout << ans.size() << endl;for(int x:ans){cout << x << endl;}}