結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-10-12 00:41:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 1,071 bytes |
コンパイル時間 | 2,520 ms |
コンパイル使用メモリ | 204,280 KB |
最終ジャッジ日時 | 2025-01-25 00:12:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {int N,M;cin >> N >> M;vector<int>A(N);vector<pair<int,int>>C(N);for(int i = 0; i < N; i++) {cin >> A[i];C[i] = {A[i],i};}sort(C.begin(),C.end());vector<vector<int>>road(N);for(int i = 0; i < M; i++) {int u,v;cin >> u >> v;u--;v--;road[u].push_back(v);road[v].push_back(u);}int K;cin >> K;vector<int>tmp(N);for(int i = 0; i < K; i++) {int B;cin >> B;B--;tmp[B] = 1;}vector<int>ans;for(int i = 0; i < N; i++) {if(tmp[C[i].second]) {ans.push_back(C[i].second+1);for(int j = 0; j < road[C[i].second].size(); j++) {if(C[i].first < A[road[C[i].second][j]]) {tmp[road[C[i].second][j]] ^= 1;}}}}cout << ans.size() << endl;for(int i = 0; i < ans.size(); i++) {cout << ans[i] << endl;}}