245112026-02-12 10:56:59Pedri26Legtávolabbi leszármazottcpp17Időlimit túllépés 16/50400ms2360 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
int n, osapa, tav[100001], levelek;
bool volte[100001], volteapa[100001], level[100001];
struct bencu
{
    int apa;
    int fia;
}a[100001];

void szbejar(int j)
{
    int vsor[100001], elso=1, utolso=1, elozo[100001];
    bool l[100001]={0};
    vsor[elso]=j;
    l[vsor[elso]]=false;
    tav[vsor[elso]]=0;
    elozo[vsor[elso]]=vsor[elso];
    while(elso<=utolso)
    {
        tav[vsor[elso]]=tav[elozo[vsor[elso]]]+1;
        for(int i=1;i<=n;i++)
        {
            if(a[i].apa==vsor[elso] && !l[a[i].fia])
            {
                if(!level[a[i].fia]){
                utolso++;
                vsor[utolso]=a[i].fia;
                elozo[a[i].fia]=vsor[elso];
                }
                else tav[a[i].fia]=tav[a[i].apa]+1;
            }
        }
        elso++;
    }
}

int main() {
	
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].apa>>a[i].fia;
        volte[a[i].fia]=true;
        volteapa[a[i].apa]=true;
    }
    //for(int i=1;i<=n;i++)cout<<i<<"-"<<volteapa[i]<<endl;
    for(int i=1;i<=n;i++)
    {
        if(!volte[i])
        {
            osapa=i;
        }
        if(!volteapa[i])
        {
            level[i]=true;
            //cout<<i<<" ";
        }
    }
    //for(int i=1;i<=n;i++)if(level[i])cout<<i<<" ";
    //cout<<osapa;
    szbejar(osapa);
    int maxtav=INT_MIN, maxtavindex;
    for(int i=1;i<=n;i++)
    {
        if(tav[i]>maxtav)
        {
            maxtav=tav[i];
            maxtavindex=i;
        }
    }
    cout<<maxtavindex;
    
    
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base16/50
1Elfogadva0/01ms316 KiB
2Időlimit túllépés0/0377ms2140 KiB
3Elfogadva1/11ms508 KiB
4Elfogadva3/31ms508 KiB
5Elfogadva3/31ms360 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms564 KiB
8Elfogadva1/12ms564 KiB
9Időlimit túllépés0/2400ms2216 KiB
10Időlimit túllépés0/3400ms2160 KiB
11Elfogadva3/31ms564 KiB
12Időlimit túllépés0/4400ms2360 KiB
13Időlimit túllépés0/4388ms2356 KiB
14Elfogadva3/350ms580 KiB
15Időlimit túllépés0/3384ms2104 KiB
16Időlimit túllépés0/3400ms2156 KiB
17Időlimit túllépés0/3377ms2100 KiB
18Időlimit túllépés0/4386ms1844 KiB
19Időlimit túllépés0/4377ms2100 KiB
20Időlimit túllépés0/4400ms2224 KiB