#648760 (C++17) No.1477 Lamps on Graph

• 問題: No.1477 Lamps on Graph
• ユーザー: y61mpnl
• 提出日時: 2021-04-16 21:47:18
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,038 bytes
• コンパイル時間: 2,267 ms
• コンパイル使用メモリ: 209,428 KB
• 実行使用メモリ: 10,880 KB
• 最終ジャッジ日時: 2024-07-03 01:15:50
• 合計ジャッジ時間: 6,303 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	WA	-
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	39 ms; 6,528 KB
testcase_13	AC	38 ms; 6,272 KB
testcase_14	AC	49 ms; 6,784 KB
testcase_15	AC	22 ms; 5,376 KB
testcase_16	AC	15 ms; 5,376 KB
testcase_17	AC	14 ms; 5,376 KB
testcase_18	AC	39 ms; 7,552 KB
testcase_19	AC	35 ms; 6,656 KB
testcase_20	AC	15 ms; 5,376 KB
testcase_21	AC	34 ms; 6,856 KB
testcase_22	AC	11 ms; 5,376 KB
testcase_23	AC	29 ms; 5,376 KB
testcase_24	AC	56 ms; 7,372 KB
testcase_25	AC	21 ms; 5,376 KB
testcase_26	AC	48 ms; 7,748 KB
testcase_27	AC	25 ms; 5,376 KB
testcase_28	AC	30 ms; 6,272 KB
testcase_29	AC	29 ms; 5,504 KB
testcase_30	AC	20 ms; 5,592 KB
testcase_31	AC	16 ms; 5,504 KB
testcase_32	AC	63 ms; 10,480 KB
testcase_33	AC	60 ms; 9,468 KB
testcase_34	WA	-
testcase_35	AC	81 ms; 9,112 KB
testcase_36	AC	75 ms; 9,112 KB
testcase_37	AC	68 ms; 9,216 KB
testcase_38	AC	74 ms; 9,116 KB
testcase_39	AC	77 ms; 9,116 KB

ソースコード

#include<bits/stdc++.h>
#define REP(i,b,e) for(int i=(b);i<(e);i++)

int main(){
	int n, m;
	scanf("%d %d", &n, &m);

	int a[n];
	REP(i, 0, n) scanf("%d", &a[i]);

	int in[n] = {};
	std::vector<int> links[n];
	REP(i, 0, m){
		int u, v;
		scanf("%d %d", &u, &v);
		u--, v--;
		if(a[u]<a[v]){
			links[u].push_back(v);
			in[v]++;
		}else{
			links[v].push_back(u);
			in[u]++;
		}
	}

	bool on[n] = {};
	int k;
	scanf("%d", &k);
	REP(i, 0, k){
		int b;
		scanf("%d", &b);
		on[b-1] = true;
	}

	std::queue<int> que;
	REP(i, 0, n) if(in[i]==0) que.push(i);

	std::vector<int> ans;
	while(!que.empty()){
		int from = que.front();
		que.pop();

		if(!on[from]){
			for(int to: links[from]){
				if(--in[to]==0) que.push(to);
			}
		}else{
			on[from] ^= 1;
			ans.push_back(from+1);
			for(int to: links[from]){
				on[to] ^= 1;
				if(--in[to]==0) que.push(to);
			}
		}
	}

	bool ok = true;
	REP(i, 0, n) if(on[i]) ok = false;
	if(!ok) puts("-1");
	else{
		printf("%ld\n", ans.size());
		for(int x: ans) printf("%d\n", x);
	}

	return 0;
}