24612023-01-13 10:50:15TuruTamasTom és Jerry 3cpp11Wrong answer 11/5086ms9356 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_visit(vector<bool> &visited, vvig, int a, vi &d) {
    visited[a] = true;
    for (int x: graph[a]) {
        if (visited[x] || d[x] <= K) continue;
        dfs_visit(visited, graph, x, d);
    }
}

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;
        if (K > N) {
            cout << "IGEN\n";
            for (size_t i = 0; i < N - 1; i++)
            {
                cin >> a >> b;
            }
            continue;
        }

        vector<vi> graph(N);

        bool f = false;
        for (size_t i = 0; i < N - 1; i++)
        {
            cin >> a >> b;
            a--; b--;
            if ((a == Tom && b == Jerry) || (b == Tom && a == Jerry)) {
                f = true;
            }
            if (!f){
                graph[a].push_back(b);
                graph[b].push_back(a);
            }
        }
        if (f) {
            cout << "IGEN\n";
            continue;
        }
        
        vi d_tom(N, -1);
        int max_d_tom = bfs(d_tom, graph, Tom);

        if(d_tom[Jerry] == 1)
        {
            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 = (bfs(d2, graph, max_d_tom) + 1)/2;
        // if (K == 1 && nagy_tav >= 4) {
        //     cout << "NEM\n";
        //     continue;
        // }
        cout << (nagy_tav <= K ? "IGEN\n" : "NEM\n");
    } // q (question)
    cout << '\n';
}
SubtaskSumTestVerdictTimeMemory
base11/50
1Wrong answer0/03ms1828 KiB
2Wrong answer0/02ms2060 KiB
3Wrong answer0/52ms2264 KiB
4Wrong answer0/13ms2464 KiB
5Wrong answer0/13ms2656 KiB
6Wrong answer0/13ms2728 KiB
7Wrong answer0/13ms2860 KiB
8Wrong answer0/13ms2924 KiB
9Wrong answer0/13ms3052 KiB
10Wrong answer0/13ms3252 KiB
11Wrong answer0/23ms3352 KiB
12Wrong answer0/23ms3348 KiB
13Wrong answer0/13ms3476 KiB
14Accepted2/282ms6464 KiB
15Wrong answer0/279ms5076 KiB
16Wrong answer0/286ms6408 KiB
17Wrong answer0/281ms7684 KiB
18Accepted2/285ms6760 KiB
19Wrong answer0/285ms6532 KiB
20Wrong answer0/257ms9356 KiB
21Wrong answer0/276ms5548 KiB
22Wrong answer0/276ms5540 KiB
23Wrong answer0/382ms8172 KiB
24Accepted2/283ms7140 KiB
25Accepted3/382ms6940 KiB
26Wrong answer0/282ms8520 KiB
27Accepted2/276ms5676 KiB
28Wrong answer0/376ms5680 KiB