24192023-01-13 08:55:45rennTom és Jerry 3cpp11Wrong answer 2/50166ms7772 KiB
#include <bits/stdc++.h>
using namespace std;

typedef vector<vector<int>> gr;
typedef pair<int, int> pii;

inline int bfs(gr &graf, int kezdo, vector<int> &tavok)
{
    queue<int> next;
    next.push(kezdo);

    int i;
    while(!next.empty())
    {
        i = next.front();
        next.pop();

        for(auto &x : graf[i])
        {
            if(tavok[x] > -1) continue;

            next.push(x);
            tavok[x] = tavok[i]+1;
        }
    }

    return i;
}

inline int bfsm(gr &graf, int kezdo)
{
    queue<int> next;
    next.push(kezdo);
    vector<int> tavok(graf.size(), -1);
    vector<int> prev(graf.size(), -1);

    int i, j;
    while(!next.empty())
    {
        i = next.front();
        next.pop();

        for(auto &x : graf[i])
        {
            if(tavok[x] > -1) continue;

            prev[x] = i;
            next.push(x);
            tavok[x] = tavok[i]+1;
        }
    }

    j = tavok[i]/2;
 
    j = ((tavok[j] & 1)^1) ? tavok[j]+1 : tavok[j];

    return j;
}

int jerry(gr &graf, int j, int &t, vector<int> &tomtavok)
{
    vector<int> jertavok(graf.size(), -1);
    jertavok[j] = 0;

    queue<int> next;
    next.push(j);

    int i, m = -1;
    while(!next.empty())
    {
        i = next.front();
        next.pop();

        for(auto &x : graf[i])
        {
            if(jertavok[x] > -1 || tomtavok[x] <= jertavok[i]+2) continue;

            next.push(x);
            jertavok[x] = jertavok[i]+1;
        }
    }

    return jertavok[i];
}

int main()
{
    int T;
    cin >> T;

    int n, t, j, k, nn, a, b;
    int kozep;

    while(T--)
    {
        cin >> n >> t >> j >> k;
        j--;
        t--;
        nn = n-1;

        gr graf(n);
        
        vector<int> tomtavok(n, -1);
        tomtavok[t] = 0;

        while(nn--)
        {
            cin >> a >> b;

            a--; b--;
            graf[a].push_back(b);
            graf[b].push_back(a);

        }

        nn = t;
        
        nn = bfs(graf, nn, tomtavok);

        if(tomtavok[j] <= k)
        {
            cout << "IGEN\n";
            continue;
        }

        if(jerry(graf, j, t, tomtavok) < k)
        {
            cout << "IGEN\n";
            continue;
        }

        kozep = bfsm(graf, nn);

        cout << (kozep <= k ? "IGEN" : "NEM") << "\n";
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Accepted0/03ms1808 KiB
2Wrong answer0/03ms2060 KiB
3Wrong answer0/52ms2264 KiB
4Accepted1/13ms2316 KiB
5Wrong answer0/13ms2784 KiB
6Wrong answer0/13ms2792 KiB
7Wrong answer0/13ms2864 KiB
8Accepted1/13ms3104 KiB
9Wrong answer0/13ms3300 KiB
10Wrong answer0/13ms3328 KiB
11Wrong answer0/23ms3336 KiB
12Wrong answer0/23ms3416 KiB
13Wrong answer0/13ms3408 KiB
14Wrong answer0/2166ms6008 KiB
15Wrong answer0/2149ms5104 KiB
16Wrong answer0/2162ms6276 KiB
17Wrong answer0/2151ms7668 KiB
18Wrong answer0/2162ms6532 KiB
19Wrong answer0/2163ms6440 KiB
20Wrong answer0/2101ms7520 KiB
21Wrong answer0/2149ms5288 KiB
22Wrong answer0/2149ms5292 KiB
23Wrong answer0/3150ms7772 KiB
24Wrong answer0/2162ms6592 KiB
25Wrong answer0/3162ms6624 KiB
26Wrong answer0/2150ms7708 KiB
27Wrong answer0/2149ms5416 KiB
28Wrong answer0/3149ms5544 KiB