結果

問題 No.2431 Viral Hotel
ユーザー noya2noya2
提出日時 2023-08-14 21:56:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 1,487 bytes
コンパイル時間 1,834 ms
コンパイル使用メモリ 205,336 KB
最終ジャッジ日時 2025-02-16 08:09:57
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll,int>;
int main(){
int n, k, m, p; cin >> n >> k >> m >> p;
vector<vector<int>> g(n);
while (m--){
int u, v; cin >> u >> v; u--, v--;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector<ll> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
/*
0 : none
1 : infected
2 : cured
3 : infected again
*/
vector<ll> status(n,0);
priority_queue<pli,vector<pli>,greater<pli>> pque;
auto id = [&](ll t, int type){
return t * 3 + type;
};
while (k--){
int x; cin >> x; x--;
pque.push(pli(id(0,2),x));
}
int ans = 0;
while (!pque.empty()){
auto [tt, v] = pque.top(); pque.pop();
ll t = tt / 3;
int type = tt % 3;
if (type == 0){
if (status[v] == 3) continue;
status[v] = 2;
}
if (type == 1){
if (status[v] == 3) continue;
for (int u : g[v]){
pque.push(pli(id(t,2),u));
}
}
if (type == 2){
if (status[v] >= 2) continue;
if (status[v] == 0){
status[v] = 1;
pque.push(pli(id(t+s[v],1),v));
pque.push(pli(id(t+p,0),v));
}
else {
ans++;
status[v] = 3;
}
}
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0