結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 21:04:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 2,553 bytes |
コンパイル時間 | 2,261 ms |
コンパイル使用メモリ | 199,552 KB |
最終ジャッジ日時 | 2025-01-20 19:14:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#define _DEBUG#include "bits/stdc++.h"//#include <atcoder/all>#define CHOOSE(a) CHOOSE2 a#define CHOOSE2(a0,a1,a2,a3,a4,a5,x,...) x#define debug_1(x1) cout<<#x1<<": "<<x1<<endl#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl#define debug_6(x1,x2,x3,x4,x5,x6) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<", "#x6<<": "<<x6<<endl#ifdef _DEBUG#define debug(...) CHOOSE((__VA_ARGS__,debug_6,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)#else#define debug(...)#endif#define rep(index,num) for(int index=0;index<(int)num;index++)#define rep1(index,num) for(int index=1;index<=(int)num;index++)#define brep(index,num) for(int index=(int)num-1;index>=0;index--)#define brep1(index,num) for(int index=(int)num;index>0;index--)#define scan(argument) cin>>argument#define prin(argument) cout<<argument<<endl#define kaigyo cout<<endl#define eps 1e-7#define mp(a1,a2) make_pair(a1,a2)#define ALL(a) (a).begin(),(a).end()#define rALL(a) (a).rbegin(),(a).rend()#define puba(a) emplace_back(a)#define pubamp(a,b) emplace_back(mp(a,b))typedef long long ll;typedef long double ld;using namespace std;//using namespace atcoder;typedef pair<ll,ll> pll;typedef pair<int,int> pint;typedef vector<int> vint;typedef vector<ll> vll;typedef vector<pint> vpint;typedef vector<pll> vpll;template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }ll INFl=(ll)1e+18+1;int INF=1e+9+1;vint adj[100001];bool on[100001];int A[100001];int main(){int N,M;scan(N>>M);rep(i,N) scan(A[i]);rep(i,M){int u,v;scan(u>>v);u--; v--;if(A[u]<A[v]) adj[u].puba(v);if(A[v]<A[u]) adj[v].puba(u);}priority_queue<pint> pq;int K;scan(K);rep(k,K){int u;scan(u);u--;on[u]=1;pq.push(mp(-A[u],u));}vint ans;while(!pq.empty()){int u=pq.top().second;pq.pop();if(!on[u]){continue;}on[u]=0;ans.puba(u);for(const auto& v:adj[u]){on[v]^=1;if(on[v]) pq.push(mp(-A[v],v));}}prin(ans.size());for(const auto& u:ans){prin(u+1);}return 0;}