24022023-01-12 16:49:56TuruTamasTom és Jerry 3cpp11Wrong answer 2/50764ms130120 KiB
#include <bits/stdc++.h>
using namespace std;

int T, N, Tom, Jerry, K;

#define vvig vector<vector<int>> &graph
#define vi vector<int>

void 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);
        }
    }
}

void dfs_shortest_path(vvig, vi &path, int a, int &b, int dist, bool &end, vector<bool> &visited) {
    path.push_back(a);
    visited[a] = true;
    for (int x : graph[a]) {
        if (visited[x]) continue;
        if (end) {
            return;
        }
        if (x == b) {
            path.push_back(b);
            end = true;
        }
        else {
            dfs_shortest_path(graph, path, x, b, dist + 1, end, visited);
        }
    }
    if (!end) path.pop_back();
}

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 + 1) 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";
            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) && K > 0) {
                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);
        bfs(d_tom, graph, Tom);

        bool success = false;
        {
        vector<bool> visited(N, false);
        bool end = false;
        dfs_Jerry(graph, d_tom, Jerry, visited, 0, success, end);
        }
        // cout << success << '\n';
        if (!success) { 
            cout << "IGEN\n";
            continue;
        }

        int max_d_tom = 0;        
        for (size_t i = 0; i < d_tom.size(); i++)
        {
            max_d_tom = d_tom[max_d_tom] < d_tom[i] ? i : max_d_tom;
        }
        
        vi d2(N, -1);
        bfs(d2, graph, max_d_tom);
        int max_d2 = 0;
        for (size_t i = 0; i < d_tom.size(); i++)
        {
            max_d2 = d2[max_d2] < d2[i] ? i : max_d2;
        }
        
        vi path;
        {
        bool end = false;
        vector<bool> visited(N, false);
        dfs_shortest_path(graph, path, max_d2, max_d_tom, 0, end, visited);
        }
        int middle = path[path.size()/2];
        // cout << middle << '\n';
        vi d_middle(N, -1);

        bfs(d_middle, graph, middle);
        int counter = 0;
        vector<bool> visited(N, false);
        for (size_t i = 0; i < d_middle.size(); i++)
        {
            if (visited[i] || d_middle[i] < K) continue;
            counter++;
            dfs_visit(visited, graph, i, d_middle);
        }
        // cout << counter << '\n';
        if (counter >= 2) cout << "NEM\n";
        else cout << "IGEN\n";
    } // q (question)
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Accepted0/03ms1960 KiB
2Accepted0/02ms2224 KiB
3Wrong answer0/52ms2540 KiB
4Wrong answer0/13ms2900 KiB
5Wrong answer0/13ms3080 KiB
6Wrong answer0/13ms3428 KiB
7Wrong answer0/13ms3620 KiB
8Wrong answer0/13ms3592 KiB
9Wrong answer0/13ms3756 KiB
10Wrong answer0/13ms3780 KiB
11Wrong answer0/23ms3800 KiB
12Wrong answer0/23ms3940 KiB
13Wrong answer0/13ms4028 KiB
14Wrong answer0/2250ms20524 KiB
15Wrong answer0/2437ms19936 KiB
16Wrong answer0/2605ms27936 KiB
17Runtime error0/2324ms130120 KiB
18Wrong answer0/2391ms32400 KiB
19Accepted2/2531ms14896 KiB
20Runtime error0/271ms130068 KiB
21Wrong answer0/2472ms26224 KiB
22Wrong answer0/2173ms11164 KiB
23Time limit exceeded0/3764ms53956 KiB
24Wrong answer0/2356ms38856 KiB
25Wrong answer0/3119ms18360 KiB
26Runtime error0/2469ms129288 KiB
27Wrong answer0/2221ms17216 KiB
28Wrong answer0/397ms8180 KiB