1426 | 2022. 09. 10 18:21:25 | kideso | Tom és Jerry 3 | cpp17 | Elfogadva 50/50 | 172ms | 9360 KiB |
#include <iostream>
#include <queue>
using namespace std;
const int maxN = 30001;
vector<int> x[maxN];
int tav[maxN][3];
bool l[maxN][3];
int N, K, i, a, b, T, J, s, m, tipus;
bool jo;
void mely(int p){
l[p][tipus] = true;
for(auto index : x[p])
if(!l[index][tipus]){
tav[index][tipus] = tav[p][tipus] + 1;
mely(index);
}
}
void megold(){
cin >> N >> T >> J >> K;
for(i = 1; i < N; ++i){
cin >> a >> b;
x[a].push_back(b);
x[b].push_back(a);
}
tipus = 0;
mely(T);
tipus = 1;
mely(J);
s = 0;
m = 0;
for(i = 1; i <= N; ++i)
if(m < tav[i][0]){
m = tav[i][0];
s = i;
}
tipus = 2;
mely(s);
m = 0;
for(i = 1; i <= N; ++i)
m = max(m, tav[i][2]);
jo = true;
for(i = 1; i <= N; ++i)
if(tav[i][0] > tav[i][1] + 1 && tav[i][0] > K)
jo = false;
cout << ((jo || m <= 2 * K) ? "IGEN\n" : "NEM\n");
for(i = 1; i <= N; ++i){
tav[i][0] = tav[i][1] = tav[i][2] = 0;
l[i][0] = l[i][1] = l[i][2] = false;
x[i].clear();
}
}
int main(){
int t;
cin >> t;
while(t--)
megold();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 4ms | 3416 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 3572 KiB | |||
3 | Elfogadva | 5/5 | 3ms | 3636 KiB | |||
4 | Elfogadva | 1/1 | 4ms | 3640 KiB | |||
5 | Elfogadva | 1/1 | 4ms | 3932 KiB | |||
6 | Elfogadva | 1/1 | 4ms | 3844 KiB | |||
7 | Elfogadva | 1/1 | 4ms | 4100 KiB | |||
8 | Elfogadva | 1/1 | 4ms | 4044 KiB | |||
9 | Elfogadva | 1/1 | 4ms | 4304 KiB | |||
10 | Elfogadva | 1/1 | 4ms | 4600 KiB | |||
11 | Elfogadva | 2/2 | 4ms | 4412 KiB | |||
12 | Elfogadva | 2/2 | 4ms | 4564 KiB | |||
13 | Elfogadva | 1/1 | 4ms | 4724 KiB | |||
14 | Elfogadva | 2/2 | 171ms | 6928 KiB | |||
15 | Elfogadva | 2/2 | 146ms | 5848 KiB | |||
16 | Elfogadva | 2/2 | 172ms | 6864 KiB | |||
17 | Elfogadva | 2/2 | 165ms | 7700 KiB | |||
18 | Elfogadva | 2/2 | 172ms | 6840 KiB | |||
19 | Elfogadva | 2/2 | 167ms | 7336 KiB | |||
20 | Elfogadva | 2/2 | 115ms | 9360 KiB | |||
21 | Elfogadva | 2/2 | 149ms | 6420 KiB | |||
22 | Elfogadva | 2/2 | 143ms | 6776 KiB | |||
23 | Elfogadva | 3/3 | 164ms | 9032 KiB | |||
24 | Elfogadva | 2/2 | 172ms | 7876 KiB | |||
25 | Elfogadva | 3/3 | 165ms | 8124 KiB | |||
26 | Elfogadva | 2/2 | 172ms | 8904 KiB | |||
27 | Elfogadva | 2/2 | 148ms | 6948 KiB | |||
28 | Elfogadva | 3/3 | 143ms | 7276 KiB |