13732022-08-28 12:35:22csandrasTom és Jerry 3cpp11Hibás válasz 7/50200ms35612 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);
    for (int i = 0; i < G.size(); ++i)
    {
        if (dist_J[i] == K && dist_T[i] < K)
        {
            return true;
        }
    }
    return false;
}

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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base7/50
1Elfogadva0/03ms1808 KiB
2Hibás válasz0/03ms2068 KiB
3Elfogadva5/52ms2292 KiB
4Elfogadva1/14ms2632 KiB
5Hibás válasz0/14ms2736 KiB
6Hibás válasz0/14ms2964 KiB
7Hibás válasz0/13ms3040 KiB
8Elfogadva1/13ms3068 KiB
9Hibás válasz0/14ms3504 KiB
10Hibás válasz0/14ms3268 KiB
11Hibás válasz0/23ms3500 KiB
12Hibás válasz0/23ms3736 KiB
13Hibás válasz0/13ms3984 KiB
14Hibás válasz0/2199ms8760 KiB
15Hibás válasz0/2173ms9816 KiB
16Hibás válasz0/2185ms13296 KiB
17Hibás válasz0/2174ms16612 KiB
18Hibás válasz0/2200ms17452 KiB
19Hibás válasz0/2177ms19484 KiB
20Hibás válasz0/2120ms24532 KiB
21Hibás válasz0/2168ms21320 KiB
22Hibás válasz0/2160ms23476 KiB
23Hibás válasz0/3190ms28448 KiB
24Hibás válasz0/2200ms29120 KiB
25Hibás válasz0/3192ms31116 KiB
26Hibás válasz0/2194ms34884 KiB
27Hibás válasz0/2180ms33836 KiB
28Hibás válasz0/3173ms35612 KiB