結果
問題 | No.1477 Lamps on Graph |
ユーザー |
|
提出日時 | 2021-04-16 22:27:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 1,690 bytes |
コンパイル時間 | 2,083 ms |
コンパイル使用メモリ | 204,956 KB |
最終ジャッジ日時 | 2025-01-20 20:11:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; (i) < (int)(n); ++(i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i)) #define REP_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i)) #define REP3R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i)) #define ALL(x) ::std::begin(x), ::std::end(x) using namespace std; vector<int> solve(int n, int m, const vector<int64_t>& a, const vector<int>& u, const vector<int>& v, int k, const vector<int>& b) { vector<vector<int> > g(n); REP (i, m) { if (a[u[i]] < a[v[i]]) g[u[i]].push_back(v[i]); if (a[v[i]] < a[u[i]]) g[v[i]].push_back(u[i]); } vector<int> order(n); iota(ALL(order), 0); sort(ALL(order), [&](int x, int y) { return a[x] < a[y]; }); vector<bool> used(n); for (int b_i : b) { used[b_i] = true; } vector<int> ans; for (int x : order) { if (used[x]) { ans.push_back(x); for (int y : g[x]) { used[y] = not used[y]; } } } return ans; } // generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); constexpr char endl = '\n'; int N, M; cin >> N; cin >> M; vector<int64_t> A(N); REP (i, N) { cin >> A[i]; } vector<int> u(M), v(M); REP (i, M) { cin >> u[i] >> v[i]; -- u[i]; -- v[i]; } int K; cin >> K; vector<int> B(K); REP (i, K) { cin >> B[i]; -- B[i]; } auto ans = solve(N, M, A, u, v, K, B); cout << ans.size() << endl; REP (i, ans.size()) { cout << ans[i] + 1 << endl; } return 0; }