結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:23:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,531 bytes |
コンパイル時間 | 831 ms |
コンパイル使用メモリ | 102,504 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-07-03 02:22:57 |
合計ジャッジ時間 | 4,016 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
/* -*- coding: utf-8 -*-** 1477.cc: No.1477 Lamps on Graph - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 100000;/* typedef */typedef vector<int> vi;typedef queue<int> qi;/* global variables */int as[MAX_N], pns[MAX_N], xs[MAX_N];vi nbrs[MAX_N];bool ls[MAX_N];/* subroutines *//* main */int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) scanf("%d", as + i);for (int i = 0; i < m; i++) {int u, v;scanf("%d%d", &u, &v);u--, v--;if (as[u] < as[v]) nbrs[u].push_back(v), pns[v]++;else if (as[u] > as[v]) nbrs[v].push_back(u), pns[u]++;}int k;scanf("%d", &k);for (int i = 0; i < k; i++) {int bi;scanf("%d", &bi);bi--;ls[bi] = true;}qi q;for (int i = 0; i < n; i++)if (pns[i] == 0) q.push(i);int xn = 0;while (! q.empty()) {int u = q.front(); q.pop();if (ls[u]) xs[xn++] = u;vi &nbru = nbrs[u];for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {int v = *vit;ls[v] ^= ls[u];if (--pns[v] == 0) q.push(v);}}printf("%d\n", xn);for (int i = 0; i < xn; i++) printf("%d\n", xs[i] + 1);return 0;}