3886 | 2023. 03. 03 14:47:31 | Erik_Gepard | Tom és Jerry 1 (80) | cpp17 | Elfogadva 80/80 | 193ms | 24564 KiB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> tgraf[100009];
vector<int> jgraf[100009];
vector<int> ttav;
vector<int> jtav;
vector<int> tvolt;
vector<int> jvolt;
void solve(){
int n, m, t, p, e;
cin>>n>>m>>t>>p>>e;
ttav.assign(n+1, INT_MAX);
jtav.assign(n+1, INT_MAX);
tvolt.assign(n+1, 0);
jvolt.assign(n+1, 0);
for(int i=0; i<m; i++){
int a, b, c;
cin>>a>>b>>c;
if(c==2){
tgraf[a].pb(b);
tgraf[b].pb(a);
}
jgraf[a].pb(b);
jgraf[b].pb(a);
}
ttav[t]=0;
tvolt[t]=1;
queue<int> q;
q.push(t);
while(!q.empty()){
int elso=q.front();
q.pop();
for(int szom : tgraf[elso]){
if(!tvolt[szom]){
ttav[szom]=ttav[elso]+1;
tvolt[szom]=1;
q.push(szom);
}
}
}
jtav[e]=0;
jvolt[e]=1;
priority_queue<pair<int, int>> pq;
pq.push({ttav[e], e});
while(!pq.empty()){
pair<int, int> elso=pq.top();
pq.pop();
if(elso.first>=0){
jvolt[elso.second]=true;
for(int szom : jgraf[elso.second]){
if(!jvolt[szom]){
pq.push({min(ttav[szom]-1, elso.first-1),szom});
}
}
}
}
for(int i=0; i<p; i++){
int a;
cin>>a;
if(jvolt[a]) cout<<"IGEN\n";
else cout<<"NEM\n";
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 80/80 | ||||||
1 | Elfogadva | 0/0 | 6ms | 11400 KiB | |||
2 | Elfogadva | 0/0 | 8ms | 11760 KiB | |||
3 | Elfogadva | 4/4 | 6ms | 11596 KiB | |||
4 | Elfogadva | 4/4 | 6ms | 11516 KiB | |||
5 | Elfogadva | 4/4 | 6ms | 11780 KiB | |||
6 | Elfogadva | 4/4 | 6ms | 11876 KiB | |||
7 | Elfogadva | 4/4 | 6ms | 12032 KiB | |||
8 | Elfogadva | 4/4 | 7ms | 12592 KiB | |||
9 | Elfogadva | 4/4 | 8ms | 12708 KiB | |||
10 | Elfogadva | 4/4 | 7ms | 12712 KiB | |||
11 | Elfogadva | 4/4 | 17ms | 13708 KiB | |||
12 | Elfogadva | 4/4 | 12ms | 13588 KiB | |||
13 | Elfogadva | 4/4 | 28ms | 14880 KiB | |||
14 | Elfogadva | 4/4 | 59ms | 17208 KiB | |||
15 | Elfogadva | 4/4 | 193ms | 24564 KiB | |||
16 | Elfogadva | 4/4 | 50ms | 19888 KiB | |||
17 | Elfogadva | 4/4 | 67ms | 21196 KiB | |||
18 | Elfogadva | 4/4 | 79ms | 19644 KiB | |||
19 | Elfogadva | 4/4 | 57ms | 19388 KiB | |||
20 | Elfogadva | 4/4 | 48ms | 19068 KiB | |||
21 | Elfogadva | 4/4 | 39ms | 17664 KiB | |||
22 | Elfogadva | 4/4 | 136ms | 23952 KiB |