SHARE
TWEET

Untitled

a guest Jul 19th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int preorder[1000000+5];
  6. vector<int> sasiedzi[1000000+5];
  7. int roz[1000000+5];
  8. bool odwiedzone[1000000+5];
  9.  
  10. int temp_preorder = 1;
  11. int n;
  12.  
  13.  
  14. long long max_sciezka;
  15. long long suma_sciezek;
  16.  
  17.  
  18. int i=0;
  19.  
  20. int make_Roz(int w)
  21. {
  22.     i++;
  23.     cout<<i<<endl;
  24.     if(roz[w] != -1)
  25.         return roz[w];
  26.     else
  27.     {
  28.         odwiedzone[w] = true;
  29.         int temp_roz = 1;
  30.         int ile_sas = sasiedzi[w].size();
  31.         for(int i=0; i<ile_sas; i++)
  32.         {
  33.             if(odwiedzone[sasiedzi[w][i]] == false)
  34.                 temp_roz += make_Roz(sasiedzi[w][i]);
  35.  
  36.         }
  37.  
  38.         roz[w] = temp_roz;
  39.         i--;
  40.         return temp_roz;
  41.     }
  42.  
  43. }
  44.  
  45. void DFS(int w, long long dot_dlug)
  46. {
  47.    odwiedzone[w] = true;
  48.    dot_dlug++;
  49.  
  50.    suma_sciezek+=(2*dot_dlug);
  51.    // cout<<"DODAJE 2 RAZY SCIEZKE DO: "<<w<<" rowna "<<dot_dlug<<endl;
  52.    bool poszedlem_dalej = false;
  53.    int ile_sas = sasiedzi[w].size();
  54.    for(int i=0; i<ile_sas; i++)
  55.    {
  56.         if(odwiedzone[sasiedzi[w][i]] == false)
  57.         {
  58.             DFS(sasiedzi[w][i], dot_dlug);
  59.             poszedlem_dalej=true;
  60.         }
  61.    }
  62.  
  63.     if(poszedlem_dalej == false)
  64.        max_sciezka = max(max_sciezka, dot_dlug);
  65.  
  66. }
  67.  
  68. void DFS_bez_drugiego_C(int w, long long dot_dlug, int drugie_C)
  69. {
  70.    odwiedzone[w] = true;
  71.    if(w == drugie_C)
  72.     return;
  73.    dot_dlug++;
  74.  
  75.     //cout<<"DODAJE 2 RAZY SCIEZKE DO (B2C): "<<w<<" rowna "<<dot_dlug<<endl;
  76.    bool poszedlem_dalej = false;
  77.    int ile_sas = sasiedzi[w].size();
  78.    for(int i=0; i<ile_sas; i++)
  79.    {
  80.         if(odwiedzone[sasiedzi[w][i]] == false)
  81.         {
  82.             DFS_bez_drugiego_C(sasiedzi[w][i], dot_dlug, drugie_C);
  83.             poszedlem_dalej=true;
  84.         }
  85.    }
  86.  
  87.    if(poszedlem_dalej == false)
  88.         max_sciezka = max(max_sciezka, dot_dlug);
  89.  
  90. }
  91.  
  92.  
  93.  
  94. int main()
  95. {
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(0);
  98.  
  99.     cin>>n;
  100.  
  101.  
  102.  
  103.     int t1;
  104.     int t2;
  105.     for(int i=1; i<n; i++)
  106.     {
  107.         cin>>t1;
  108.         cin>>t2;
  109.         sasiedzi[t1].push_back(t2);
  110.         sasiedzi[t2].push_back(t1);
  111.     }
  112.  
  113.     if(n==2)
  114.     {
  115.  
  116.         cout<<1<<endl;
  117.         cout<<1<<endl;
  118.         return 0;
  119.     }
  120.     ///STWORZENIE TABLICY OJCOW I SYNOW
  121.     /*cout<<"FATHER"<<endl;
  122.     for(int i=1; i<=n; i++)
  123.         cout<<i<<": "<<father[i]<<endl;*/
  124.  
  125.  
  126.     for(int i=1; i<=n; i++)
  127.         roz[i] = -1;
  128.  
  129.     make_Roz(1);
  130.    // make_Preorder(1);
  131.  
  132.    for(int i=0; i<=n; i++)
  133.         odwiedzone[i] = false;
  134.  
  135.    bool found_C = false;
  136.    int ind = 1;
  137.  
  138.    while(found_C == false)
  139.    {
  140.         found_C = true;
  141.         int ile_sas = sasiedzi[ind].size();
  142.         for(int i=0; i<ile_sas; i++)
  143.         {
  144.             if(roz[sasiedzi[ind][i]] > n/2)
  145.             {
  146.                 found_C = false;
  147.                 roz[ind] -= roz[sasiedzi[ind][i]];
  148.                 roz[sasiedzi[ind][i]] = n;
  149.  
  150.                 ind = sasiedzi[ind][i];
  151.                 i=ile_sas+10;
  152.  
  153.             }
  154.         }
  155.    }
  156.    int Centroid1 = ind;
  157.  
  158.    bool found_C2 = false;
  159.  
  160.    ///DLA KAZDEGO SASIADA CENTROIDU 1 SPRAWDZ CZY TEZ NIE JEST CENTROIDEM
  161.  
  162.    int ile_sas = sasiedzi[Centroid1].size();
  163.    int Centroid2 = -1;
  164.  
  165.    ///POMIMO PETLI W PETLI W SUMIE ROZPATRZYMY KAZDY WIERZCHOLEK MAX 1 RAZ -> O(n)
  166.    for(int i=0; i<ile_sas; i++)
  167.    {
  168.         int kandydat = sasiedzi[Centroid1][i];
  169.  
  170.         roz[Centroid1] -= roz[kandydat];
  171.         roz[kandydat] = n;
  172.  
  173.         int ile_sas_kandydata = sasiedzi[kandydat].size();
  174.         bool foundC2 = true;
  175.         for(int j=0; j<ile_sas_kandydata; j++)
  176.         {
  177.             if(roz[sasiedzi[kandydat][j]] > n/2)
  178.             {
  179.                 foundC2 = false;
  180.                 j=ile_sas+10;
  181.             }
  182.         }
  183.  
  184.         if(foundC2 == true)
  185.             {Centroid2 = kandydat; break;}
  186.  
  187.  
  188.         roz[kandydat] -= roz[Centroid1];
  189.         roz[Centroid1] = n;
  190.    }
  191.  
  192.  
  193.  
  194.    ///ZNALEZNIONO CENTROID(Y)
  195.    //cout<<Centroid1<<" "<<Centroid2<<endl;
  196.  
  197.     max_sciezka = 0;
  198.     suma_sciezek = 0;
  199.     DFS(Centroid1, -1);
  200.     long long dlu_C1 = suma_sciezek - max_sciezka;
  201.     long long dlu_C2;
  202.  
  203.     //cout<<"CENT1: "<<Centroid1<<" dlu1:" <<dlu_C1<<" max_sciezka: "<<max_sciezka<<endl;
  204.  
  205.     if(Centroid2!=-1)
  206.     {
  207.  
  208.         for(int i=0; i<=n; i++)
  209.             odwiedzone[i] = false;
  210.  
  211.                 max_sciezka = 0;
  212.  
  213.         DFS_bez_drugiego_C(Centroid2, 0, Centroid1);
  214.         dlu_C1 = suma_sciezek - max_sciezka;
  215.  
  216.  
  217.  
  218.  
  219.        // cout<<"TERAZ C2"<<endl;
  220.         max_sciezka = 0;
  221.         suma_sciezek = 0;
  222.  
  223.         for(int i=0; i<=n; i++)
  224.             odwiedzone[i] = false;
  225.         DFS(Centroid2, -1);
  226.  
  227.         for(int i=0; i<=n; i++)
  228.             odwiedzone[i] = false;
  229.         max_sciezka = 0;
  230.         DFS_bez_drugiego_C(Centroid1, 0, Centroid2);
  231.  
  232.         dlu_C2 = suma_sciezek - max_sciezka;
  233.  
  234.  
  235.     }
  236.  //   cout<<"CENT1: "<<Centroid1<<" dlu1:" <<dlu_C1<<" max_sciezka: "<<max_sciezka<<endl;
  237.    // cout<<"CENT2: "<<Centroid2<<" dlu2:" <<dlu_C2<<" max_sciezka: "<<max_sciezka<<endl;
  238.  
  239.  
  240.     for(int i=1; i<=n; i++)
  241.     {
  242.         if(i==Centroid1)
  243.             cout<<dlu_C1<<'\n';
  244.         else if(i==Centroid2)
  245.             cout<<dlu_C2<<'\n';
  246.         else
  247.             cout<<-1<<'\n';
  248.  
  249.  
  250.     }
  251.  
  252.     return 0;
  253. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top