Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <climits>
- using namespace std;
- vector <int> sas [100005];
- vector <int> synowie[100005];
- bool odw[100005];
- int father[100005];
- int nim_baz[100005];
- int spr_mexow[100005];
- int spr_mexow2[100005];
- int spr_mexow3[100005];
- int nim[100005];
- int temp_nim[100005];
- int ost_nim[100005];
- int mexy_drzew[100005];
- int prefix_xor[100005];
- int sufiks_xor[100005];
- int global_n = 0;
- int wyw_make_temp = 0;
- void zeruj_odw()
- {
- for(int i=1; i<=global_n; i++)
- odw[i] = 0;
- }
- void DFS_make_tree(int i)
- {
- odw[i] = 1;
- int ile_sas = sas[i].size();
- for(int j=0; j<ile_sas; j++)
- if(!odw[sas[i][j]])
- {
- father[sas[i][j]] = i;
- synowie[i].push_back(sas[i][j]);
- DFS_make_tree(sas[i][j]);
- }
- }
- void DFS_nim_baz(int i)
- {
- odw[i] = 1;
- int ile_synow = synowie[i].size();
- if(ile_synow==0)
- {
- nim_baz[i] = 0; ///POZYCJA PRZEGRYWAJACA
- return;
- }
- else
- {
- for(int j=0; j<ile_synow; j++)
- DFS_nim_baz(synowie[i][j]);
- nim_baz[i] = 0;
- ///DLA KAZDEGO SYNA
- for(int j=0; j<ile_synow; j++)
- {
- ///ZAZNACZAM W TABLICY SPR_MEXOW INDEKS I
- spr_mexow[nim_baz[synowie[i][j]]] = i;
- }
- for(int j=0; j<=100000; j++)
- if(spr_mexow[j] != i)
- {nim_baz[i] = j; return; }
- }
- }
- void make_temp(int ja, int nieleg_syn)
- {
- // cout<<"MAKE TEMP DLA PARAMETROW: ja: "<<ja<<" niel_syn: "<<nieleg_syn<<endl;
- ///LICZE MEXA Z TEMPOW DLA MNIE ZASTEPUJAC NIMI JEDNOCZESNIE MOJ TEMP, LEGALNY JEST OJCEIC, JESLI NIE JEST MNÄ„ I SYNOWIE OPROCZ NIELEGALNEGO
- if(father[ja] != ja)
- { spr_mexow[temp_nim[father[ja]]] = wyw_make_temp; //cout<<temp_nim[father[ja]]<<'\t';
- }
- int ile_synow = synowie[ja].size();
- for(int i=0; i<ile_synow; i++)
- {
- if(synowie[ja][i] != nieleg_syn)
- { spr_mexow[temp_nim[synowie[ja][i]]] = wyw_make_temp; //cout<<temp_nim[synowie[ja][i]]<<'\t';
- }
- }
- for(int j=0; j<=100000; j++)
- if(spr_mexow[j] != wyw_make_temp)
- {temp_nim[ja] = j; //cout<<endl; cout<<"ZWRACAM: "<<j<<endl; cout<<endl;
- return; }
- }
- void DFS_nim(int i)
- {
- // cout<<"WYWOLANO DSF_NIM: "<<i<<endl;
- odw[i] = 1;
- int ile_synow = synowie[i].size();
- if(father[i]==i)
- ost_nim[i] = nim_baz[i];
- else
- {
- ///na bazie temp_nim ojca i synow tworze wlasny ost_nim
- ///JA JESTEM NOWYM KORZENIEM czyt. zmienia sie orien. miedzy ojcem a mna
- ///musze policzyc nowy temp dla ojca
- wyw_make_temp++;
- make_temp(father[i], i);
- spr_mexow2[temp_nim[father[i]]] = i;
- for(int j=0; j<ile_synow; j++)
- spr_mexow2[temp_nim[synowie[i][j]]] = i;
- for(int j=0; j<=100000; j++)
- if(spr_mexow2[j] != i)
- {ost_nim[i] = j; j=100000+5;}
- }
- for(int j=0; j<ile_synow; j++)
- DFS_nim(synowie[i][j]);
- temp_nim[i] = nim_baz[i];
- //temp_nim[father[i]] = nim_baz[father[i]];
- // cout<<"WYCHODZE Z DFS_NIM: "<<i<<"WYNIK OST: "<<ost_nim[i]<<endl;
- //cout<<endl;
- }
- void DFS_mex(int i, int gdzie_mex)
- {
- odw[i] = 1;
- int ile_synow = synowie[i].size();
- for(int j=0; j<ile_synow; j++)
- {
- spr_mexow3[ost_nim[synowie[i][j]]] = gdzie_mex;
- DFS_mex(synowie[i][j], gdzie_mex);
- }
- }
- int make_mexy_drzew(int i)
- {
- mexy_drzew[i] = ost_nim[i];
- spr_mexow3[ost_nim[i]] = i;
- ///PUSZCZAM DFS PO DRZEWIE I XOROJE MEXY DRZEW I
- DFS_mex(i, i);
- for(int j=0; j<=100000; j++)
- if(spr_mexow3[j] != i)
- {mexy_drzew[i] = j; j=100000+5;}
- return mexy_drzew[i];
- }
- int main()
- {
- int k;
- int n;
- cin>>k;
- int a;
- int b;
- for(int i=1; i<=k; i++)
- {
- cin>>n;
- for(int j=1; j<=n-1; j++)
- {
- cin>>a;
- cin>>b;
- sas[global_n+a].push_back(global_n+b);
- sas[global_n+b].push_back(global_n+a);
- }
- global_n+=n;
- }
- // cout<<global_n<<endl;
- ///STWORZ DRZEWA
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- {
- father[i] = i;
- DFS_make_tree(i);
- }
- // for(int i=1; i<=global_n; i++)
- // cout<<"i: "<<i<<" father: "<<father[i]<<endl;
- zeruj_odw();
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- DFS_nim_baz(i);
- // for(int i=1; i<=global_n; i++)
- // cout<<"i: "<<i<<" nim_baz: "<<nim_baz[i]<<endl;
- // cout<<endl;
- // cout<<endl;
- ///DOTAD OK
- zeruj_odw();
- for(int i=0; i<=100005; i++)
- spr_mexow[i] = 0;
- for(int i=1; i<=global_n; i++)
- temp_nim[i] = nim_baz[i];
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- DFS_nim(i);
- //for(int i=1; i<=global_n; i++)
- // cout<<"i: "<<i<<" ost_nim: "<<ost_nim[i]<<endl;
- // return 0;
- ///DOTAD OK, KORZYSTAMY TERAZ TYLKO Z OST_NIM JAKO ZBIORU NIM SUM
- /// DLA KAZDEGO WIERZCHOLKA KTORY JEST KORZENIEM W TABLICY "MEXY" DAJEMY MEXA Z DRZEWA
- ///DLA WIERZCHOLKOW NIE-KORZENI ZAPISUJE 0 - NIE ZMIENI TO WYNIKU XORA
- zeruj_odw();
- vector<pair<int, int>> mexy; ///mexy kolejnych drzew i numery ich korzeni
- for(int i=1; i<=global_n; i++)
- if(!odw[i])
- mexy.push_back(make_pair(make_mexy_drzew(i), i));
- int xor_ = 0;
- for(int i=0; i<mexy.size(); i++)
- xor_ = xor_ ^ mexy[i].first;
- if(xor_ == 0)
- {cout<<0; return 0;}
- int result = 0;
- mexy.push_back(make_pair(0,global_n+1)); ///potrzebne by poznac koniec realnie ostatinego drzewa
- ///DLA KAZDEGO DRZEWA
- for(int i=0; i<mexy.size()-1; i++)
- {
- xor_ = xor_ ^ mexy[i].first;
- for(int j=mexy[i].second; j<mexy[i+1].second; j++)
- {
- if(!(xor_ ^ ost_nim[j]))
- result++;
- }
- xor_ = xor_ ^ mexy[i].first;
- }
- cout<<result;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement