13742022-08-28 12:38:48csandrasTom és Jerry 3cpp11Wrong answer 5/50199ms10020 KiB
#include <bits/stdc++.h>

using namespace std;

using Graph = vector<vector<int>>;


void dfs(int p, const Graph& G, vector<int>& dist, vector<bool>& visited)
{
    visited[p] = true;
    for (int q : G[p])
    {
        if (!visited[q])
        {
            dist[q] = dist[p] + 1;
            dfs(q, G, dist, visited);
        }
    }
}

vector<int> distances_from(int start, const Graph& G)
{
    vector<int> dist(G.size(), -1);
    dist[start] = 0;
    vector<bool> visited(G.size(), false);
    dfs(start, G, dist, visited);
    return dist;
}

int diameter(const Graph& G)
{
    vector<int> dist = distances_from(0, G);
    int start = max_element(dist.begin(), dist.end()) - dist.begin();
    vector<int> dist2 = distances_from(start, G);
    return *max_element(dist2.begin(), dist2.end());
}

bool can_caught_in_K_step(const Graph& G, int TS, int JS, int K)
{
    vector<int> dist_T = distances_from(TS, G);
    vector<int> dist_J = distances_from(JS, G);
    bool can_caught = true;
    for (int i = 0; i < G.size(); ++i)
    {
        if (dist_J[i] == K && dist_T[i] > K)
        {
            can_caught = false;
        }
    }
    return can_caught;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int N, TS, JS, K;
        cin >> N >> TS >> JS >> K;
        --TS, --JS;
        vector<vector<int>> G(N);
        for (int i = 0; i < N-1; ++i)
        {
            int u, v;
            cin >> u >> v;
            --u, --v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        if (diameter(G) <= 2*K || can_caught_in_K_step(G, TS, JS, K))
        {
            cout << "IGEN\n";
        }
        else
        {
            cout << "NEM\n";
        }
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base5/50
1Wrong answer0/03ms2088 KiB
2Wrong answer0/03ms2240 KiB
3Wrong answer0/52ms2248 KiB
4Accepted1/13ms2500 KiB
5Wrong answer0/13ms2704 KiB
6Wrong answer0/14ms2828 KiB
7Wrong answer0/13ms2944 KiB
8Wrong answer0/13ms2900 KiB
9Wrong answer0/13ms2900 KiB
10Wrong answer0/13ms3032 KiB
11Wrong answer0/23ms3148 KiB
12Wrong answer0/23ms3032 KiB
13Wrong answer0/13ms3280 KiB
14Wrong answer0/2199ms5948 KiB
15Wrong answer0/2163ms4900 KiB
16Wrong answer0/2184ms6188 KiB
17Wrong answer0/2173ms7572 KiB
18Wrong answer0/2197ms6332 KiB
19Accepted2/2174ms6188 KiB
20Wrong answer0/2119ms10020 KiB
21Wrong answer0/2167ms4976 KiB
22Accepted2/2159ms4900 KiB
23Wrong answer0/3189ms7768 KiB
24Wrong answer0/2199ms6188 KiB
25Wrong answer0/3193ms6176 KiB
26Wrong answer0/2195ms8140 KiB
27Wrong answer0/2178ms4992 KiB
28Wrong answer0/3173ms5020 KiB