2454 | 2023. 01. 13 10:31:25 | renn | Tom és Jerry 3 | cpp11 | Elfogadva 50/50 | 90ms | 9484 KiB |
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
typedef vector<vector<long>> gr;
typedef pair<long, long> pii;
inline long bfs(gr &graf, long kezdo, vector<long> &tavok)
{
queue<long> next;
next.push(kezdo);
long i;
while(!next.empty())
{
i = next.front();
next.pop();
for(auto &x : graf[i])
{
if(tavok[x] > -1) continue;
next.push(x);
tavok[x] = tavok[i]+1;
}
}
return i;
}
inline long bfsm(gr &graf, long kezdo)
{
queue<long> next;
next.push(kezdo);
vector<long> tavok(graf.size(), -1);
long i, j;
while(!next.empty())
{
i = next.front();
next.pop();
for(auto &x : graf[i])
{
if(tavok[x] > -1) continue;
next.push(x);
tavok[x] = tavok[i]+1;
}
}
j = tavok[i]/2;
//j = (j & 1)^1 ? j+1 : j;
return j;
}
long jerry(gr &graf, long j, long &t, vector<long> &tomtavok)
{
vector<long> jertavok(graf.size(), -1);
jertavok[j] = 0;
queue<long> next;
next.push(j);
long m = j;
long i;
while(!next.empty())
{
i = next.front();
next.pop();
for(auto &x : graf[i])
{
if(jertavok[x] > -1 || tomtavok[x] <= jertavok[i]+2) continue;
next.push(x);
jertavok[x] = jertavok[i]+1;
m = tomtavok[m] > tomtavok[x] ? m : x;
}
}
return m > -1 ? tomtavok[m] : tomtavok[i];
}
int main()
{
InTheNameOfGod
long T;
cin >> T;
long n, t, j, k, nn, a, b;
long kozep;
while(T--)
{
cin >> n >> t >> j >> k;
j--;
t--;
nn = n-1;
gr graf(n);
vector<long> tomtavok(n, -1);
tomtavok[t] = 0;
while(nn--)
{
cin >> a >> b;
a--; b--;
graf[a].push_back(b);
graf[b].push_back(a);
}
nn = t;
nn = bfs(graf, nn, tomtavok);
if(tomtavok[j] == 1)
{
cout << "IGEN\n";
continue;
}
if(jerry(graf, j, t, tomtavok) <= k)
{
cout << "IGEN\n";
continue;
}
kozep = bfsm(graf, nn);
cout << (kozep < k ? "IGEN" : "NEM") << "\n";
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 2ms | 2024 KiB | |||
3 | Elfogadva | 5/5 | 2ms | 2224 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2440 KiB | |||
5 | Elfogadva | 1/1 | 3ms | 2656 KiB | |||
6 | Elfogadva | 1/1 | 3ms | 2856 KiB | |||
7 | Elfogadva | 1/1 | 3ms | 2952 KiB | |||
8 | Elfogadva | 1/1 | 3ms | 3160 KiB | |||
9 | Elfogadva | 1/1 | 3ms | 3224 KiB | |||
10 | Elfogadva | 1/1 | 3ms | 3356 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3568 KiB | |||
12 | Elfogadva | 2/2 | 3ms | 3780 KiB | |||
13 | Elfogadva | 1/1 | 3ms | 3976 KiB | |||
14 | Elfogadva | 2/2 | 87ms | 7236 KiB | |||
15 | Elfogadva | 2/2 | 81ms | 6120 KiB | |||
16 | Elfogadva | 2/2 | 90ms | 7748 KiB | |||
17 | Elfogadva | 2/2 | 83ms | 9484 KiB | |||
18 | Elfogadva | 2/2 | 89ms | 7624 KiB | |||
19 | Elfogadva | 2/2 | 89ms | 7928 KiB | |||
20 | Elfogadva | 2/2 | 59ms | 9272 KiB | |||
21 | Elfogadva | 2/2 | 79ms | 6252 KiB | |||
22 | Elfogadva | 2/2 | 79ms | 6348 KiB | |||
23 | Elfogadva | 3/3 | 83ms | 9248 KiB | |||
24 | Elfogadva | 2/2 | 87ms | 8012 KiB | |||
25 | Elfogadva | 3/3 | 86ms | 7808 KiB | |||
26 | Elfogadva | 2/2 | 83ms | 9320 KiB | |||
27 | Elfogadva | 2/2 | 79ms | 6300 KiB | |||
28 | Elfogadva | 3/3 | 79ms | 6276 KiB |