結果

問題 No.1477 Lamps on Graph
ユーザー ぷらぷら
提出日時 2021-10-12 00:41:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 291 ms / 2,000 ms
コード長 1,071 bytes
コンパイル時間 2,520 ms
コンパイル使用メモリ 204,280 KB
最終ジャッジ日時 2025-01-25 00:12:35
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N,M;
    cin >> N >> M;
    vector<int>A(N);
    vector<pair<int,int>>C(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        C[i] = {A[i],i};
    }
    sort(C.begin(),C.end());
    vector<vector<int>>road(N);
    for(int i = 0; i < M; i++) {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        road[u].push_back(v);
        road[v].push_back(u);
    }
    int K;
    cin >> K;
    vector<int>tmp(N);
    for(int i = 0; i < K; i++) {
        int B;
        cin >> B;
        B--;
        tmp[B] = 1;
    }
    vector<int>ans;
    for(int i = 0; i < N; i++) {
        if(tmp[C[i].second]) {
            ans.push_back(C[i].second+1);
            for(int j = 0; j < road[C[i].second].size(); j++) {
                if(C[i].first < A[road[C[i].second][j]]) {
                    tmp[road[C[i].second][j]] ^= 1;
                }
            }
        }
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
}
0