3928 2023. 03. 05 19:07:36 hackemon Legtávolabbi leszármazott cpp17 Elfogadva 50/50 37ms 15652 KiB
#include <bits/stdc++.h>
using namespace std;
//using namespace std::chrono;

#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vl vector<ll>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvl vector<vl>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fScan {ios_base::sync_with_stdio(false); cin.tie(NULL);}
#define rep(i, a, b) for(int i = a; i < (b); i++)
#define REP(i, n) for(int i = 0;i <(n); i++)
using ll = long long;
using ld = long double;
ll mod = 1000000007;

const char ny =  '\n';

bool prime(ll a) {
    if (a==1) return 0;
    for (int i=2;i*i<=a;++i)
    {
        if (a%i==0) return 0;
    }
    return 1;
}

ll gcd(ll a,ll b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}

ll min(int a, ll b) {
    if(a< b) return a;
    else return b;
}

int n;
vector<vector<int>> adj(100005);
int os = 1;
vector<int> be(100005, 0), dist(100005, 0);

void bfs(int kezdo) {
    dist[kezdo] = 0;
    queue<int> most;
    most.push(kezdo);
    while(!most.empty()) {
        int x = most.front();
        most.pop();
        for(int i = 0;i< adj[x].size();i++) {
            dist[adj[x][i]] = dist[x]+1;
            most.push(adj[x][i]);
        }
    }
}


void solve() { 
    cin >> n;
    for(int i = 0;i< n-1;i++ ){ 
        int a, b;
        cin >> a >> b;
        be[b]++;
        adj[a].push_back(b);
    }
    for(int i = 1;i<=n;i++ ) {
        if(!be[i]) {
            os = i;
            break;
        }
    }
    bfs(os);
    int ma = 0, ans = 1;
    for(int i = 1;i<=n;i++ ) {
        if(dist[i] > ma) {
            ma = dist[i];
            ans = i;
        }
    }
    cout << ans << ny;
}


int main()
{
    fScan

    int t = 1;
    //comment out if necessary
    //cin>> t;


    //auto start = high_resolution_clock::now();
    while(t-- ) {
        solve();
    }
    //auto end = high_resolution_clock::now();
    //auto dur = duration_cast<milliseconds>(end-start);
    //cout<< "runtime: " << dur.count() << " milliseconds" << '\n';
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 4ms 7912 KiB
2 Elfogadva 0/0 34ms 11368 KiB
3 Elfogadva 1/1 4ms 8400 KiB
4 Elfogadva 3/3 4ms 8620 KiB
5 Elfogadva 3/3 4ms 8904 KiB
6 Elfogadva 1/1 4ms 8908 KiB
7 Elfogadva 1/1 4ms 9196 KiB
8 Elfogadva 1/1 4ms 9096 KiB
9 Elfogadva 2/2 35ms 12332 KiB
10 Elfogadva 3/3 35ms 12332 KiB
11 Elfogadva 3/3 4ms 9276 KiB
12 Elfogadva 4/4 37ms 13516 KiB
13 Elfogadva 4/4 35ms 13768 KiB
14 Elfogadva 3/3 8ms 10080 KiB
15 Elfogadva 3/3 32ms 14572 KiB
16 Elfogadva 3/3 32ms 13880 KiB
17 Elfogadva 3/3 34ms 13740 KiB
18 Elfogadva 4/4 27ms 13176 KiB
19 Elfogadva 4/4 30ms 13568 KiB
20 Elfogadva 4/4 37ms 15652 KiB