SHARE
TWEET

Untitled

a guest Aug 20th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. using namespace std;
  5.  
  6. vector <int> sas [100005];
  7. vector <int> synowie[100005];
  8. bool odw[100005];
  9. int father[100005];
  10. int nim_baz[100005];
  11. int spr_mexow[100005];
  12. int spr_mexow2[100005];
  13. int spr_mexow3[100005];
  14. int nim[100005];
  15. int temp_nim[100005];
  16. int ost_nim[100005];
  17. int mexy_drzew[100005];
  18.  
  19.  
  20. int prefix_xor[100005];
  21. int sufiks_xor[100005];
  22.  
  23.  
  24. int global_n = 0;
  25. int wyw_make_temp = 0;
  26.  
  27. void zeruj_odw()
  28. {
  29.     for(int i=1; i<=global_n; i++)
  30.         odw[i] = 0;
  31. }
  32.  
  33. void DFS_make_tree(int i)
  34. {
  35.     odw[i] = 1;
  36.  
  37.     int ile_sas = sas[i].size();
  38.     for(int j=0; j<ile_sas; j++)
  39.         if(!odw[sas[i][j]])
  40.         {
  41.             father[sas[i][j]] = i;
  42.             synowie[i].push_back(sas[i][j]);
  43.             DFS_make_tree(sas[i][j]);
  44.         }
  45. }
  46.  
  47. void DFS_nim_baz(int i)
  48. {
  49.     odw[i] = 1;
  50.  
  51.     int ile_synow = synowie[i].size();
  52.  
  53.     if(ile_synow==0)
  54.     {
  55.         nim_baz[i] = 0; ///POZYCJA PRZEGRYWAJACA
  56.         return;
  57.     }
  58.  
  59.     else
  60.     {
  61.         for(int j=0; j<ile_synow; j++)
  62.             DFS_nim_baz(synowie[i][j]);
  63.  
  64.         nim_baz[i] = 0;
  65.  
  66.         ///DLA KAZDEGO SYNA
  67.         for(int j=0; j<ile_synow; j++)
  68.         {
  69.             ///ZAZNACZAM W TABLICY SPR_MEXOW INDEKS I
  70.             spr_mexow[nim_baz[synowie[i][j]]] = i;
  71.         }
  72.  
  73.         for(int j=0; j<=100000; j++)
  74.             if(spr_mexow[j] != i)
  75.                 {nim_baz[i] = j;  return; }
  76.     }
  77. }
  78.  
  79. void make_temp(int ja, int nieleg_syn)
  80. {
  81.    // cout<<"MAKE TEMP DLA PARAMETROW: ja: "<<ja<<" niel_syn: "<<nieleg_syn<<endl;
  82.     ///LICZE MEXA Z TEMPOW DLA MNIE ZASTEPUJAC NIMI JEDNOCZESNIE MOJ TEMP, LEGALNY JEST OJCEIC, JESLI NIE JEST MNĄ I SYNOWIE OPROCZ NIELEGALNEGO
  83.     if(father[ja] != ja)
  84.         { spr_mexow[temp_nim[father[ja]]] = wyw_make_temp; //cout<<temp_nim[father[ja]]<<'\t';
  85.         }
  86.  
  87.     int ile_synow = synowie[ja].size();
  88.     for(int i=0; i<ile_synow; i++)
  89.     {
  90.         if(synowie[ja][i] != nieleg_syn)
  91.             { spr_mexow[temp_nim[synowie[ja][i]]] = wyw_make_temp; //cout<<temp_nim[synowie[ja][i]]<<'\t';
  92.             }
  93.  
  94.     }
  95.  
  96.         for(int j=0; j<=100000; j++)
  97.             if(spr_mexow[j] != wyw_make_temp)
  98.                 {temp_nim[ja] = j; //cout<<endl; cout<<"ZWRACAM: "<<j<<endl; cout<<endl;
  99.                 return; }
  100. }
  101.  
  102. void DFS_nim(int i)
  103. {
  104. //    cout<<"WYWOLANO DSF_NIM: "<<i<<endl;
  105.  
  106.     odw[i] = 1;
  107.     int ile_synow = synowie[i].size();
  108.  
  109.     if(father[i]==i)
  110.         ost_nim[i] = nim_baz[i];
  111.  
  112.     else
  113.     {
  114.     ///na bazie temp_nim ojca i synow tworze wlasny ost_nim
  115.  
  116.         ///JA JESTEM NOWYM KORZENIEM czyt. zmienia sie orien. miedzy ojcem a mna
  117.         ///musze policzyc nowy temp dla ojca
  118.             wyw_make_temp++;
  119.             make_temp(father[i], i);
  120.             spr_mexow2[temp_nim[father[i]]] = i;
  121.  
  122.         for(int j=0; j<ile_synow; j++)
  123.             spr_mexow2[temp_nim[synowie[i][j]]] = i;
  124.  
  125.         for(int j=0; j<=100000; j++)
  126.             if(spr_mexow2[j] != i)
  127.                 {ost_nim[i] = j; j=100000+5;}
  128.  
  129.     }
  130.  
  131.  
  132.     for(int j=0; j<ile_synow; j++)
  133.         DFS_nim(synowie[i][j]);
  134.  
  135.     temp_nim[i] = nim_baz[i];
  136.     //temp_nim[father[i]] = nim_baz[father[i]];
  137.  
  138.    // cout<<"WYCHODZE Z DFS_NIM: "<<i<<"WYNIK OST: "<<ost_nim[i]<<endl;
  139.     //cout<<endl;
  140.     }
  141.  
  142. void DFS_mex(int i, int gdzie_mex)
  143. {
  144.     odw[i] = 1;
  145.     int ile_synow = synowie[i].size();
  146.     for(int j=0; j<ile_synow; j++)
  147.     {
  148.         spr_mexow3[ost_nim[synowie[i][j]]] = gdzie_mex;
  149.         DFS_mex(synowie[i][j], gdzie_mex);
  150.     }
  151. }
  152.  
  153.  
  154. int make_mexy_drzew(int i)
  155. {
  156.  
  157.     mexy_drzew[i] = ost_nim[i];
  158.     spr_mexow3[ost_nim[i]] = i;
  159.     ///PUSZCZAM DFS PO DRZEWIE I XOROJE MEXY DRZEW I
  160.     DFS_mex(i, i);
  161.  
  162.  
  163.    for(int j=0; j<=100000; j++)
  164.             if(spr_mexow3[j] != i)
  165.                 {mexy_drzew[i] = j; j=100000+5;}
  166.     return mexy_drzew[i];
  167.  
  168. }
  169.  
  170.  
  171.  
  172.  
  173. int main()
  174. {
  175.     int k;
  176.     int n;
  177.  
  178.     cin>>k;
  179.  
  180.     int a;
  181.     int b;
  182.     for(int i=1; i<=k; i++)
  183.     {
  184.         cin>>n;
  185.         for(int j=1; j<=n-1; j++)
  186.         {
  187.             cin>>a;
  188.             cin>>b;
  189.  
  190.             sas[global_n+a].push_back(global_n+b);
  191.             sas[global_n+b].push_back(global_n+a);
  192.         }
  193.         global_n+=n;
  194.     }
  195.  //   cout<<global_n<<endl;
  196.  
  197.     ///STWORZ DRZEWA
  198.     for(int i=1; i<=global_n; i++)
  199.         if(!odw[i])
  200.         {
  201.             father[i] = i;
  202.             DFS_make_tree(i);
  203.  
  204.         }
  205.  
  206.   //  for(int i=1; i<=global_n; i++)
  207.     //    cout<<"i: "<<i<<" father: "<<father[i]<<endl;
  208.  
  209.     zeruj_odw();
  210.  
  211.     for(int i=1; i<=global_n; i++)
  212.         if(!odw[i])
  213.             DFS_nim_baz(i);
  214.  
  215.  
  216.  
  217. //    for(int i=1; i<=global_n; i++)
  218.   //      cout<<"i: "<<i<<" nim_baz: "<<nim_baz[i]<<endl;
  219.  
  220. //    cout<<endl;
  221.   //  cout<<endl;
  222.     ///DOTAD OK
  223.  
  224.     zeruj_odw();
  225.     for(int i=0; i<=100005; i++)
  226.         spr_mexow[i] = 0;
  227.  
  228.  
  229.      for(int i=1; i<=global_n; i++)
  230.         temp_nim[i] = nim_baz[i];
  231.  
  232.  
  233.     for(int i=1; i<=global_n; i++)
  234.         if(!odw[i])
  235.             DFS_nim(i);
  236.  
  237. //for(int i=1; i<=global_n; i++)
  238.   //      cout<<"i: "<<i<<" ost_nim: "<<ost_nim[i]<<endl;
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.    // return 0;
  259.     ///DOTAD OK, KORZYSTAMY TERAZ TYLKO Z OST_NIM JAKO ZBIORU NIM SUM
  260.  
  261.     /// DLA KAZDEGO WIERZCHOLKA KTORY JEST KORZENIEM W TABLICY "MEXY" DAJEMY MEXA Z DRZEWA
  262.     ///DLA WIERZCHOLKOW NIE-KORZENI ZAPISUJE 0 - NIE ZMIENI TO WYNIKU XORA
  263.  
  264.     zeruj_odw();
  265.  
  266.     vector<pair<int, int>> mexy; ///mexy kolejnych drzew i numery ich korzeni
  267.  
  268.  
  269.     for(int i=1; i<=global_n; i++)
  270.         if(!odw[i])
  271.             mexy.push_back(make_pair(make_mexy_drzew(i), i));
  272.  
  273.  
  274.     int xor_ = 0;
  275.     for(int i=0; i<mexy.size(); i++)
  276.         xor_ = xor_ ^ mexy[i].first;
  277.  
  278.     if(xor_ == 0)
  279.     {cout<<0; return 0;}
  280.  
  281.  
  282.     int result = 0;
  283.     mexy.push_back(make_pair(0,global_n+1)); ///potrzebne by poznac koniec realnie ostatinego drzewa
  284.     ///DLA KAZDEGO DRZEWA
  285.     for(int i=0; i<mexy.size()-1; i++)
  286.     {
  287.         xor_ = xor_ ^ mexy[i].first;
  288.         for(int j=mexy[i].second; j<mexy[i+1].second; j++)
  289.         {
  290.             if(!(xor_ ^ ost_nim[j]))
  291.                 result++;
  292.         }
  293.         xor_ = xor_ ^ mexy[i].first;
  294.     }
  295.  
  296.     cout<<result;
  297.  
  298.  
  299.  
  300.  
  301.     return 0;
  302. }
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