結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:06:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 1,049 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 180,268 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-07-02 21:54:37 |
合計ジャッジ時間 | 8,276 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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); for (int i = 0; i < N; i++){ cin >> A[i]; } vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int u, v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } int K; cin >> K; vector<int> B(K); for (int i = 0; i < K; i++){ cin >> B[i]; B[i]--; } vector<pair<int, int>> P(N); for (int i = 0; i < N; i++){ P[i] = make_pair(A[i], i); } sort(P.begin(), P.end()); vector<int> id(N); for (int i = 0; i < N; i++){ id[i] = P[i].second; } vector<bool> c(N, false); for (int i = 0; i < K; i++){ c[B[i]] = true; } vector<int> x; for (int i = 0; i < N; i++){ if (c[id[i]]){ c[id[i]] = false; x.push_back(id[i]); for (int j : E[id[i]]){ if (A[id[i]] < A[j]){ c[j] = !c[j]; } } } } int Z = x.size(); cout << Z << endl; for (int i = 0; i < Z; i++){ cout << x[i] + 1 << endl; } }