結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:39:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 2,213 bytes |
コンパイル時間 | 3,585 ms |
コンパイル使用メモリ | 178,136 KB |
実行使用メモリ | 12,884 KB |
最終ジャッジ日時 | 2024-07-03 02:52:25 |
合計ジャッジ時間 | 8,715 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <iostream>#include <string>#include <cmath>#include<algorithm>#include<stack>#include<queue>#include<map>#include<set>#include<iomanip>#include<bitset>#define _USE_MATH_DEFINES#include <math.h>#include <functional>#include<complex>#include<cassert>#include<random>using namespace std;#include<atcoder/all>using namespace atcoder;#define rep(i,x) for(ll i=0;i<x;i++)#define repn(i,x) for(ll i=1;i<=x;i++)typedef long long ll;typedef pair<ll, ll> P;const ll INF = 1e17;const ll MAX = 4000001;const long double eps = 1E-14;ll max(ll a, ll b) {if (a > b) { return a; }return b;}ll min(ll a, ll b) {if (a > b) { return b; }return a;}ll gcd(ll a, ll b) {if (b == 0) { return a; }if (a < b) { return gcd(b, a); }return gcd(b, a % b);}ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}struct edge {ll id;ll fr;ll to;ll d;};using mint = modint;typedef vector<ll> vll;typedef vector <vector<ll>> vvll;typedef vector<vector<vector<ll>>> vvvll;typedef vector<mint> vmint;typedef vector<vector<mint>> vvmint;typedef vector<vector<vector<mint>>> vvvmint;vmint f, finv, inv;void cominit(ll N) {ll MOD = modint::mod();//デフォルトが998244353に注意f.assign(N + 1, 1);finv.assign(N + 1, 1);inv.assign(N + 1, 1);inv[1] = 1;repn(i, N) {f[i] = f[i - 1] * i;if (i > 1)inv[i] = -inv[MOD % i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}mint com(ll a, ll b) {if (a < 0 || b < 0 || a < b) { return 0; }return f[a] * finv[b] * finv[a - b];}/////////////////////////////////////int main() {ll N, M;cin >> N >> M;vll A(N);rep(i, N)cin >> A[i];vvll g(N);rep(i, M) {ll u, v;cin >> u >> v;u--; v--;if (A[u] < A[v]) { g[u].push_back(v); }if (A[u] > A[v]) { g[v].push_back(u); }}vll on(N);ll K;cin >> K;rep(i, K) {ll b;cin >> b;on[b - 1]++;}vector<P> p(N);rep(i, N)p[i] = { A[i],i };sort(p.begin(), p.end());vll lis;rep(i, N) {ll x = p[i].second;if (on[x] == 0) { continue; }on[x] = 0;lis.push_back(x);for (ll y : g[x]) {on[y] = 1 - on[y];}}cout << lis.size() << endl;for (ll x : lis) {cout << x + 1 << endl;}}