24752023-01-13 11:09:38TuruTamasTom és Jerry 3cpp11Elfogadva 50/5093ms8484 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 bfs_Jerry(vector<int> &d, vvig, int kezd, vi &d_tom) {
    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 || d_tom[x] < d[k] + 2) continue;
            d[x] = d[k] + 1;
            q.push(x);
        }
    }
}



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';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1824 KiB
2Elfogadva0/02ms2064 KiB
3Elfogadva5/52ms2292 KiB
4Elfogadva1/13ms2504 KiB
5Elfogadva1/13ms2684 KiB
6Elfogadva1/13ms2852 KiB
7Elfogadva1/13ms2800 KiB
8Elfogadva1/13ms3024 KiB
9Elfogadva1/13ms3136 KiB
10Elfogadva1/13ms3212 KiB
11Elfogadva2/23ms3300 KiB
12Elfogadva2/23ms3300 KiB
13Elfogadva1/13ms3212 KiB
14Elfogadva2/293ms6184 KiB
15Elfogadva2/283ms5076 KiB
16Elfogadva2/293ms6264 KiB
17Elfogadva2/286ms7684 KiB
18Elfogadva2/293ms6560 KiB
19Elfogadva2/292ms6720 KiB
20Elfogadva2/257ms7880 KiB
21Elfogadva2/283ms5508 KiB
22Elfogadva2/282ms5392 KiB
23Elfogadva3/383ms7984 KiB
24Elfogadva2/293ms7224 KiB
25Elfogadva3/390ms7164 KiB
26Elfogadva2/286ms8484 KiB
27Elfogadva2/285ms5764 KiB
28Elfogadva3/386ms5680 KiB