24652023-01-13 10:52:57rennTom és Jerry 3cpp11Hibás válasz 40/5085ms8424 KiB
#include    <bits/stdc++.h>
using namespace std;

#define InTheNameOfGod cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

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);
    tavok[kezdo] = 0;

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

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 m = j;

    int i;
    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;
            m = tomtavok[m] > tomtavok[x] ? m : x;
        }
    }
    return m > -1 ? tomtavok[m] : tomtavok[i];
}

int main()
{

    InTheNameOfGod

    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> tavok(n, -1);

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

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

        }

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

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

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

        std::fill(tavok.begin(), tavok.end(), -1);
        kozep = tavok[bfs(graf, nn, tavok)]/2;

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

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/50
1Elfogadva0/03ms1696 KiB
2Elfogadva0/02ms1864 KiB
3Hibás válasz0/52ms1936 KiB
4Elfogadva1/13ms2076 KiB
5Elfogadva1/13ms2288 KiB
6Elfogadva1/13ms2360 KiB
7Elfogadva1/13ms2492 KiB
8Hibás válasz0/13ms2696 KiB
9Elfogadva1/13ms2764 KiB
10Elfogadva1/13ms2988 KiB
11Elfogadva2/23ms2988 KiB
12Elfogadva2/23ms3200 KiB
13Elfogadva1/13ms3272 KiB
14Elfogadva2/282ms5868 KiB
15Elfogadva2/278ms4732 KiB
16Elfogadva2/285ms5988 KiB
17Hibás válasz0/281ms7308 KiB
18Elfogadva2/283ms6100 KiB
19Elfogadva2/285ms6280 KiB
20Hibás válasz0/254ms7484 KiB
21Elfogadva2/275ms5040 KiB
22Elfogadva2/275ms5460 KiB
23Elfogadva3/379ms8056 KiB
24Elfogadva2/283ms6664 KiB
25Elfogadva3/381ms6960 KiB
26Elfogadva2/279ms8424 KiB
27Elfogadva2/275ms6032 KiB
28Elfogadva3/375ms6368 KiB