結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:14:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 2,222 bytes |
コンパイル時間 | 4,312 ms |
コンパイル使用メモリ | 254,188 KB |
最終ジャッジ日時 | 2025-01-20 20:05:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing namespace std;using Graph = vector<vector<int>>;using vst= vector<string>;using vin= vector<int>;using ll=long long;using ull=unsigned long long;using vll= vector<ll>;using P=pair<int ,int>;using pqi=priority_queue<int, vector<int>, greater<int>>;using pqp=priority_queue<P, vector<P>, greater<P>>;//const long double pi=acos(-1);#define ft first#define sd second#define fn front#define pb push_back#define eb emplace_back#define it insert#define vvi vector<vector<int>>#define si(v) int((v).size())#define pq priority_queue#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rell(i,n) for (ll i=0; i< (ll)(n); i++)#define sot(x) sort(x.begin(), x.end())#define rese(x) reverse(x.begin(), x.end())#define gsot(x) sort(x.begin(), x.end(), greater<ll>());#define vnn(x,y,s,name) vector<vector<int>> name(x, vector<int>(y,s))#define mse(x) memset(x, 0, sizeof(x))#define all(x) (x).begin(),(x).end()#define mii(x,y,z) min(x,min(y,z))#define maa(x,y,z) max(x,max(y,z))#define cps CLOCKS_PER_SEC#define yes cout<<"Yes"<<"\n"#define no cout<<"No"<<"\n"#define cset(x) cout<<fixed<<setprecision(x)//const int INF=1001001001;//const ll INF=1e18;//998244353 1000000007int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int n,m;cin>>n>>m;vin a(n);pqp q;P t;rep(i,n){cin>>a[i];t.ft=a[i];t.sd=i;q.push(t);}Graph G(n);rep(i,m){int u,v;cin>>u>>v;u--;v--;G[u].eb(v);G[v].eb(u);}int k;cin>>k;vector<bool> l(n,false);rep(i,k){int b;cin>>b;b--;l[b]=true;}vector<int> r;while(!q.empty()){auto h=q.top();q.pop();if(l[h.sd]==false) continue;else{r.eb(h.sd);l[h.sd]=true;for(auto g:G[h.sd]){if(a[g]>h.ft)l[g]=(!l[g]);}}}cout<<r.size()<<endl;for(auto x:r) cout<<x+1<<endl;}