Cod sursa(job #1855089)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 23 ianuarie 2017 13:54:14
Problema Schi Scor 0
Compilator cpp Status done
Runda gym_emag_avansati_2016 Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sediu.in");
ofstream g("sediu.out");
#define N_MAX 16005
vector <int> G[N_MAX];
int n, a[N_MAX], b[N_MAX], lev;
bool viz[N_MAX];

void df(int nod)
{
    lev++;
    a[nod]++;
    viz[nod] = 1;
    for(auto it:G[nod])
    {
        if(!viz[it])
        {
            df(it);
            lev--;
            a[nod] += a[it];
            b[nod] = max(b[nod], a[it]);
        }
    }

}

int main()
{
    int x, y, minn = N_MAX, rez;
    f >> n;
    for(int i = 1; i< n ; i++)
    {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    df(1);

    for(int i = 1; i <= n; i++)
        a[i]--;

   // for(int i = 1; i <= n; i++)
      //  cout << i << " " << a[i] << " " << b[i] << "\n";

    for(int i = 1; i <= n; i++)
        b[i] = max(b[i],n-a[i]-1);

   // cout<<"\n";

   // for(int i = 1; i <= n; i++)
       // cout << a[i] << " " << b[i] << "\n";
    for(int i = 1; i <= n; i++)

        if(minn > b[i])
        {
            minn = b[i];
            rez=1;
        }
        else if(minn == b[i])
            rez++;
    g << minn << " " << rez << "\n";
    for(int i = 1; i <= n; i++)
        if(b[i] == minn)
            g<< i << " ";
    return 0;
}