24532023-01-13 10:30:30TuruTamasTom és Jerry 3cpp11Hibás válasz 18/50773ms129996 KiB
#include <bits/stdc++.h>
using namespace std;

long T, N, Tom, Jerry, K;

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

void bfs(vector<long> &d, vvig, long kezd) {
    queue<long> q;
    q.push(kezd);
    d[kezd] = 0;
    long k;
    while (!q.empty())
    {
        k = q.front();
        q.pop();
        for (long x : graph[k]) {
            if (d[x] != -1) continue;
            d[x] = d[k] + 1;
            q.push(x);
        }
    }
}

void dfs_visit(vector<bool> &visited, vvig, long a, vi &d) {
    visited[a] = true;
    for (long x: graph[a]) {
        if (visited[x] || d[x] <= K) continue;
        dfs_visit(visited, graph, x, d);
    }
}

void dfs_Jerry(vvig, vi d_tom, long loc, vector<bool> &visited, long dist, bool &success, bool &end) {
    visited[loc] = true;
    for (long 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--;
        long 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);
        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);
        }
        if (!success) {
            cout << "IGEN\n";
            continue;
        }

        long 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);
        long nagy_tav = *max_element(d2.begin(), d2.end());
        if (K == 1 && nagy_tav >= 4) {
            cout << "NEM\n";
            continue;
        }
        if (nagy_tav >= K*2 + 1) cout << "NEM\n";
        else cout << "IGEN\n";
    } // q (question)
    cout << '\n';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/50
1Elfogadva0/03ms1704 KiB
2Elfogadva0/02ms2032 KiB
3Hibás válasz0/52ms2072 KiB
4Elfogadva1/13ms2432 KiB
5Hibás válasz0/13ms2496 KiB
6Elfogadva1/13ms2848 KiB
7Hibás válasz0/13ms2904 KiB
8Elfogadva1/13ms3000 KiB
9Hibás válasz0/13ms3112 KiB
10Elfogadva1/13ms3308 KiB
11Elfogadva2/23ms3396 KiB
12Elfogadva2/23ms3520 KiB
13Elfogadva1/13ms3716 KiB
14Elfogadva2/2469ms29892 KiB
15Időlimit túllépés0/2773ms13804 KiB
16Időlimit túllépés0/2765ms17416 KiB
17Futási hiba0/2532ms129996 KiB
18Időlimit túllépés0/2769ms30048 KiB
19Időlimit túllépés0/2765ms9512 KiB
20Futási hiba0/279ms129760 KiB
21Időlimit túllépés0/2762ms24180 KiB
22Elfogadva2/2426ms9612 KiB
23Időlimit túllépés0/3757ms61744 KiB
24Időlimit túllépés0/2759ms29816 KiB
25Elfogadva3/3165ms13440 KiB
26Futási hiba0/2193ms129564 KiB
27Elfogadva2/2521ms26932 KiB
28Hibás válasz0/393ms8216 KiB