3762 | 2023. 03. 02 20:52:00 | UnluckY | Tom és Jerry 1 (80) | cpp11 | Időlimit túllépés 4/80 | 600ms | 9228 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> tom, jerry;
vector<int> tomtav;
vector<bool> seen, mego;
void dfs(int x, int mtom){
if (seen[x]) return;
seen[x] = true;
int mtomuj;
if (tomtav[x] == -1){
mtomuj = max(-1, mtom-1);
}
else if (mtom = -1){
mtomuj = tomtav[x];
}
else {
mtomuj = min(mtom-1, tomtav[x]);
}
if (mtomuj != 0) mego[x] = true;
for (int i : jerry[x]){
if (mtomuj != 0) dfs(i, mtomuj);
}
seen[x] = false;
}
int main(){
int n, m, t, p, e; cin >> n >> m >> t >> p >> e;
tom.assign(n+1, {});
jerry.assign(n+1, {});
tomtav.assign(n+1, -1);
seen.assign(n+1, false);
mego.assign(n+1, false);
for (int i = 0; i < m; i++){
int a, b, c; cin >> a >> b >> c;
jerry[a].push_back(b);
jerry[b].push_back(a);
if (c == 2){
tom[a].push_back(b);
tom[b].push_back(a);
}
}
queue<int> q;
q.push(t);
vector<bool> bfsseen(n+1, false);
tomtav[t] = 0;
while (!q.empty()){
int x = q.front(); q.pop();
//cout << x << endl;
if (bfsseen[x]) {continue;}
bfsseen[x] = true;
for (int i : tom[x]){
if (tomtav[i] == -1){tomtav[i] = tomtav[x]+1;}
else {tomtav[i] = min(tomtav[i], tomtav[x]+1);}
q.push(i);
//cout << x << " " << i << endl;
}
}
// for (int i : tomtav){
// cout << i << " ";
// }
dfs(e, -1);
for (int i = 0; i < p; i++){
int x; cin >> x;
if (mego[x]) cout << "IGEN";
else cout << "NEM";
cout << endl;
}
return 0;
}
/*
9 11 6 3 1
1 2 1
1 3 1
2 4 1
3 4 2
3 5 2
4 7 1
5 7 1
5 6 2
6 8 1
7 9 1
8 9 1
7
8
9
*/
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 4/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1812 KiB | |||
2 | Időlimit túllépés | 0/0 | 600ms | 1460 KiB | |||
3 | Elfogadva | 4/4 | 3ms | 2276 KiB | |||
4 | Hibás válasz | 0/4 | 3ms | 2476 KiB | |||
5 | Időlimit túllépés | 0/4 | 600ms | 2668 KiB | |||
6 | Időlimit túllépés | 0/4 | 578ms | 2908 KiB | |||
7 | Időlimit túllépés | 0/4 | 566ms | 3004 KiB | |||
8 | Időlimit túllépés | 0/4 | 542ms | 2320 KiB | |||
9 | Időlimit túllépés | 0/4 | 559ms | 3364 KiB | |||
10 | Időlimit túllépés | 0/4 | 570ms | 2828 KiB | |||
11 | Időlimit túllépés | 0/4 | 578ms | 3284 KiB | |||
12 | Időlimit túllépés | 0/4 | 564ms | 3728 KiB | |||
13 | Időlimit túllépés | 0/4 | 566ms | 4312 KiB | |||
14 | Időlimit túllépés | 0/4 | 566ms | 5900 KiB | |||
15 | Időlimit túllépés | 0/4 | 560ms | 6240 KiB | |||
16 | Időlimit túllépés | 0/4 | 527ms | 8672 KiB | |||
17 | Időlimit túllépés | 0/4 | 555ms | 9228 KiB | |||
18 | Időlimit túllépés | 0/4 | 568ms | 7632 KiB | |||
19 | Időlimit túllépés | 0/4 | 568ms | 8264 KiB | |||
20 | Időlimit túllépés | 0/4 | 577ms | 8264 KiB | |||
21 | Időlimit túllépés | 0/4 | 551ms | 6860 KiB | |||
22 | Időlimit túllépés | 0/4 | 555ms | 9172 KiB |