結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 21:47:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 1,984 bytes |
コンパイル時間 | 1,236 ms |
コンパイル使用メモリ | 103,468 KB |
実行使用メモリ | 11,128 KB |
最終ジャッジ日時 | 2024-07-03 01:16:05 |
合計ジャッジ時間 | 4,231 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <iostream>#include <string>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <cassert>#include <numeric>#include <functional>#include <ctime>#pragma warning(disable:4996)//#define ATCODER#ifdef ATCODER#include <atcoder/all>#endiftypedef long long ll;typedef unsigned long long ull;#define LINF 9223300000000000000#define LINF2 1223300000000000000#define LINF3 1000000000000#define INF 2140000000//const long long MOD = 1000000007;const long long MOD = 998244353;using namespace std;#ifdef ATCODERusing namespace atcoder;#endifvoid solve(){int n, m;scanf("%d%d", &n, &m);vector<int> a(n);vector<vector<int>> g(n); // tovector<pair<int, int>> z; // a[i],iint i;for (i = 0; i < n; i++) {scanf("%d", &a[i]);z.push_back(make_pair(a[i], i));}sort(z.begin(), z.end());for (i = 0; i < m; i++) {int u, v;scanf("%d%d", &u, &v); u--; v--;if (a[u] < a[v]) g[u].push_back(v);else if (a[u] > a[v]) g[v].push_back(u);}vector<int> x(n);int K;scanf("%d", &K);for (i = 0; i < K; i++) {int tmp;scanf("%d", &tmp); tmp--;x[tmp] = 1;}vector<int> ans;for (i = 0; i < n; i++) {int id = z[i].second;if (x[id]) {ans.push_back(id);int j;for (j = 0; j < (int)g[id].size(); j++) {x[g[id][j]] = 1 - x[g[id][j]];}}}printf("%d\n", (int)ans.size());for (i = 0; i < (int)ans.size(); i++) {printf("%d\n", ans[i] + 1);}return;}int main(){#if 1solve();#elseint T, t;scanf("%d", &T);for (t = 0; t < T; t++) {//printf("Case #%d: ", t + 1);solve();}#endifreturn 0;}