2474 | 2023. 01. 13 11:07:24 | TuruTamas | Tom és Jerry 3 | cpp11 | Accepted 50/50 | 90ms | 8712 KiB |
#include <bits/stdc++.h>
using namespace std;
int T, N, Tom, Jerry, K;
#define vvig vector<vector<int>> &graph
#define vi vector<int>
inline int bfs(vector<int> &d, vvig, int kezd) {
queue<int> q;
q.push(kezd);
d[kezd] = 0;
int k;
while (!q.empty())
{
k = q.front();
q.pop();
for (int x : graph[k]) {
if (d[x] != -1) continue;
d[x] = d[k] + 1;
q.push(x);
}
}
return k;
}
void dfs_Jerry(vvig, vi &d_tom, int loc, vector<bool> &visited, int dist, bool &success, bool &end) {
visited[loc] = true;
for (int x : graph[loc]) {
if (end) return;
if (visited[x] || d_tom[x] <= dist + 2) continue;
if (d_tom[x] > K) {
success = true;
end = true;
return;
}
dfs_Jerry(graph, d_tom, x, visited, dist + 1, success, end);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
for (size_t q = 0; q < T; q++)
{
cin >> N >> Tom >> Jerry >> K;
Tom--; Jerry--;
int a, b;
vector<vi> graph(N);
for (size_t i = 0; i < N - 1; i++)
{
cin >> a >> b;
a--; b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
vi d_tom(N, -1);
int max_d_tom = bfs(d_tom, graph, Tom);
if(d_tom[Jerry] == 1)
{
cout << "IGEN\n";
continue;
}
vi d_jerry(N, -1);
bfs(d_jerry, graph, Jerry);
bool f = false;
for (size_t i = 0; i < d_jerry.size(); i++)
{
if (d_tom[i] > K && d_jerry[i] + 1 < d_tom[i]) {
f = true;
break;
}
}
if (!f) {
cout << "IGEN\n";
continue;
}
// bool success = false;
// vector<bool> visited(N, false);
// bool end = false;
// dfs_Jerry(graph, d_tom, Jerry, visited, 0, success, end);
// if (!success) {
// cout << "IGEN\n";
// continue;
// }
vi d2(N, -1);
int nagy_tav = d2[bfs(d2, graph, max_d_tom)];
if (nagy_tav >= K*2 + 1) cout << "NEM\n";
else cout << "IGEN\n";
} // q (question)
cout << '\n';
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Accepted | 0/0 | 3ms | 1824 KiB | |||
2 | Accepted | 0/0 | 2ms | 2068 KiB | |||
3 | Accepted | 5/5 | 2ms | 2260 KiB | |||
4 | Accepted | 1/1 | 3ms | 2440 KiB | |||
5 | Accepted | 1/1 | 3ms | 2540 KiB | |||
6 | Accepted | 1/1 | 3ms | 2644 KiB | |||
7 | Accepted | 1/1 | 3ms | 2624 KiB | |||
8 | Accepted | 1/1 | 3ms | 2748 KiB | |||
9 | Accepted | 1/1 | 3ms | 2964 KiB | |||
10 | Accepted | 1/1 | 3ms | 3304 KiB | |||
11 | Accepted | 2/2 | 3ms | 3424 KiB | |||
12 | Accepted | 2/2 | 3ms | 3512 KiB | |||
13 | Accepted | 1/1 | 3ms | 3740 KiB | |||
14 | Accepted | 2/2 | 90ms | 6504 KiB | |||
15 | Accepted | 2/2 | 82ms | 5004 KiB | |||
16 | Accepted | 2/2 | 90ms | 6632 KiB | |||
17 | Accepted | 2/2 | 82ms | 7848 KiB | |||
18 | Accepted | 2/2 | 90ms | 6916 KiB | |||
19 | Accepted | 2/2 | 90ms | 7152 KiB | |||
20 | Accepted | 2/2 | 57ms | 8316 KiB | |||
21 | Accepted | 2/2 | 81ms | 5660 KiB | |||
22 | Accepted | 2/2 | 82ms | 5716 KiB | |||
23 | Accepted | 3/3 | 82ms | 8388 KiB | |||
24 | Accepted | 2/2 | 90ms | 7172 KiB | |||
25 | Accepted | 3/3 | 89ms | 7220 KiB | |||
26 | Accepted | 2/2 | 85ms | 8712 KiB | |||
27 | Accepted | 2/2 | 82ms | 5844 KiB | |||
28 | Accepted | 3/3 | 83ms | 6072 KiB |