結果

問題 No.1477 Lamps on Graph
ユーザー se1ka2
提出日時 2021-04-16 20:23:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 253 ms / 2,000 ms
コード長 1,300 bytes
コンパイル時間 935 ms
コンパイル使用メモリ 80,384 KB
実行使用メモリ 10,480 KB
最終ジャッジ日時 2024-07-02 22:32:57
合計ジャッジ時間 6,941 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <queue>
using namespace std;
struct Graph
{
int n;
std::vector<std::vector<int>> g;
Graph(){}
Graph(int n) : n(n){
g.resize(n);
}
void add_edge(int from, int to){
g[from].push_back(to);
}
};
int main()
{
int n, m;
cin >> n >> m;
int a[100005];
for(int i = 0; i < n; i++) cin >> a[i];
Graph g(n);
int d[100005]{0};
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
u--; v--;
if(a[u] < a[v]){
g.add_edge(u, v);
d[v]++;
}
if(a[u] > a[v]){
g.add_edge(v, u);
d[u]++;
}
}
int k;
cin >> k;
bool b[100005]{0};
for(int i = 0; i < k; i++){
int u;
cin >> u;
u--;
b[u] = true;
}
queue<int> que;
for(int u = 0; u < n; u++){
if(!d[u]) que.push(u);
}
vector<int> ans;
while(que.size()){
int u = que.front();
que.pop();
if(b[u]) ans.push_back(u);
for(int v : g.g[u]){
if(b[u]) b[v] = !b[v];
d[v]--;
if(!d[v]) que.push(v);
}
}
cout << (int)ans.size() << endl;
for(int u : ans) cout << u + 1 << endl;
cout << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0