SHARE
TWEET

Untitled

a guest Jul 18th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <array>
  4. using namespace std;
  5.  
  6. int preorder[200000+5];
  7. int father[200000+5];
  8. pair<int, int> seg_tree[550000];
  9. pair<int, int> przedz_seg_tree[550000];
  10. vector<int> sasiedzi[200000+5];
  11. vector<int> synowie[200000+5];
  12. int roz[200000+5];
  13. int uzyteczne[200000+5];
  14.  
  15. int n;
  16. int temp_preorder = 1;
  17. int max_pot = 1;
  18. int numer_grupy = 1; ///DLA SEG TREE first
  19. int czas_zmiany = 1; ///DLA SEG TREE second
  20.  
  21. void make_Tree(int w)
  22. {
  23.     int ile_sas = sasiedzi[w].size();
  24.     for(int i=0; i<ile_sas; i++)
  25.     {
  26.         if(father[sasiedzi[w][i]] == 0)
  27.         {
  28.             father[sasiedzi[w][i]] = w;
  29.             synowie[w].push_back(sasiedzi[w][i]);
  30.             make_Tree(sasiedzi[w][i]);
  31.         }
  32.     }
  33. }
  34.  
  35. void make_Preorder(int w)
  36. {
  37.     preorder[w] = temp_preorder;
  38.     temp_preorder++;
  39.     int ile_synow = synowie[w].size();
  40.     for(int i=0; i<ile_synow; i++)
  41.         make_Preorder(synowie[w][i]);
  42.  
  43. }
  44.  
  45. void change_Add(int akt_poz, int pocz, int konc, int nowa_wartosc) ///NOWA WARTOSC JEST STALA DLA CALEGO PRZEDZIALU
  46. {
  47.  
  48.     ///1. JESLI PRZEDZIAL DLA WIERZCHOLKA CALKOWICIE SIE ZAWIERA
  49.     //cout<<"JESTEM W CHANGE ADD"<<endl;
  50.  
  51.     //cout<<"akt_poz: "<<akt_poz<<" POCZ: "<<pocz<<" KONC: "<<konc<<" przedz_seg_tree[akt_poz].first: " <<przedz_seg_tree[akt_poz].first<<" przedz_seg_tree[akt_poz].second: "<<przedz_seg_tree[akt_poz].second<<endl;
  52.     if(pocz <= przedz_seg_tree[akt_poz].first && konc >= przedz_seg_tree[akt_poz].second)
  53.     {
  54.         //cout<<"PRZEDZIAL W PELNI SIE ZAWIERA W POSZUKIWANYM"<<endl;
  55.         seg_tree[akt_poz].first = nowa_wartosc;
  56.         seg_tree[akt_poz].second = czas_zmiany;
  57.         return;
  58.     }
  59.  
  60.     ///2.JESLI W OGOLE NIE JEST ZAWARTE
  61.     else if(pocz > przedz_seg_tree[akt_poz].second || konc < przedz_seg_tree[akt_poz].first)
  62.         //{cout<<"WCALE"<<endl;
  63.         {return;}
  64.  
  65.     ///3.JEST ZAWARTE CZESCIOWO
  66.     else
  67.     {
  68.         //cout<<"CZESCIOWO"<<endl;
  69.         change_Add(akt_poz*2, pocz, konc, nowa_wartosc);
  70.         change_Add(akt_poz*2+1, pocz, konc, nowa_wartosc);
  71.     }
  72. }
  73.  
  74. void change_Divide(int akt_poz, int pocz, int konc)
  75. {
  76.  
  77.     ///1. JESLI PRZEDZIAL DLA WIERZCHOLKA CALKOWICIE SIE ZAWIERA
  78.     if(pocz <= przedz_seg_tree[akt_poz].first && konc >= przedz_seg_tree[akt_poz].second)
  79.     {
  80.         seg_tree[akt_poz].first = numer_grupy;///!!!
  81.         seg_tree[akt_poz].second = czas_zmiany;
  82.         return;
  83.     }
  84.  
  85.     ///2.JESLI W OGOLE NIE JEST ZAWARTE
  86.     else if(pocz > przedz_seg_tree[akt_poz].second || konc < przedz_seg_tree[akt_poz].first)
  87.         return;
  88.  
  89.     ///3.JEST ZAWARTE CZESCIOWO
  90.     else
  91.     {
  92.         change_Divide(akt_poz*2, pocz, konc);
  93.         change_Divide(akt_poz*2+1, pocz, konc);
  94.     }
  95. }
  96.  
  97. int Find(int w)
  98. {
  99.     //cout<<"FIND dla: "<<w<<endl;
  100.     int ind = max_pot+w-1;
  101.     int najnowsza_zmiana = seg_tree[ind].second;
  102.     int akt_wartosc = seg_tree[ind].first;
  103.  
  104.     //cout<<"BAZOWE:  NAJN_ZMIANA: "<<najnowsza_zmiana<<" AKT_WA: "<<akt_wartosc<<endl;
  105.     while(ind>1)
  106.     {
  107.         //cout<<"seg_tree[ind].second: "<<seg_tree[ind].second<<" seg_tree[ind].first: "<<seg_tree[ind].first<<endl;
  108.  
  109.         if(najnowsza_zmiana < seg_tree[ind].second)
  110.             {najnowsza_zmiana = seg_tree[ind].second; akt_wartosc = seg_tree[ind].first;}
  111.  
  112.         ind/=2;
  113.     }
  114.  
  115.     if(najnowsza_zmiana < seg_tree[ind].second)
  116.             akt_wartosc = seg_tree[ind].first;
  117.  
  118.     return akt_wartosc;
  119. }
  120.  
  121. void Add(int i)
  122. {
  123.     uzyteczne[i] = true; ///!!!
  124.     czas_zmiany++;
  125.  
  126.   //  cout<<"DODAJE DLA WIERZCHOLKA: "<<i<<endl;
  127.  
  128.     int wartosc_ojca = Find(preorder[father[i]]);
  129.     seg_tree[max_pot+preorder[i]-1].first = wartosc_ojca;
  130.     seg_tree[max_pot+preorder[i]-1].second = czas_zmiany;
  131.  
  132.     //cout<<"POCZ ZMIAN: "<<preorder[i]<<" KONIEC: "<<preorder[i] + roz[i] - 1<<endl;
  133.  
  134.     change_Add(1, preorder[i],preorder[i] + roz[i] - 1,wartosc_ojca);
  135. }
  136.  
  137. void Divide(int i)
  138. {
  139.     uzyteczne[i] = false; ///!!!
  140.     czas_zmiany++;
  141.     numer_grupy++;
  142.  
  143.     seg_tree[max_pot+preorder[i]-1].first = numer_grupy;
  144.     seg_tree[max_pot+preorder[i]-1].second = czas_zmiany;
  145.  
  146.     //cout<<"DZIELE DLA WIERZCHOLKA: "<<i<<endl;
  147.     int ile_synow = synowie[i].size();
  148.     for(int j=0; j<ile_synow; j++)
  149.     {
  150.         numer_grupy++;
  151.         //cout<<"POCZ ZMIAN: "<<preorder[synowie[i][j]]<<" KONIEC: "<<preorder[synowie[i][j]]+roz[synowie[i][j]]-1<<endl;
  152.         change_Divide(1, preorder[synowie[i][j]], preorder[synowie[i][j]]+roz[synowie[i][j]]-1);
  153.     }
  154. }
  155.  
  156. void Ans(int A, int B)
  157. {
  158.     if(Find(preorder[A]) == Find(preorder[B]) && uzyteczne[A] == true && uzyteczne[B] == true)
  159.         cout<<"TAK"<<endl;
  160.     else
  161.         cout<<"NIE"<<endl;
  162.  
  163.  
  164. }
  165.  
  166.  
  167. int make_Roz(int w)
  168. {
  169.     if(roz[w] != -1)
  170.         return roz[w];
  171.     else
  172.     {
  173.         if(synowie[w].empty())
  174.             {roz[w] = 1; return 1;}
  175.         else
  176.         {
  177.             int temp=1;
  178.             int ile_sas = synowie[w].size();
  179.             for(int i=0; i<ile_sas; i++)
  180.             {
  181.                 temp+=make_Roz(synowie[w][i]);
  182.             }
  183.  
  184.             roz[w] = temp;
  185.             return temp;
  186.         }
  187.     }
  188. }
  189.  
  190. int main()
  191. {
  192.     ios_base::sync_with_stdio(0);
  193.     cin.tie(0);
  194.  
  195.     cin>>n;
  196.  
  197.     int t1;
  198.     int t2;
  199.     for(int i=1; i<n; i++)
  200.     {
  201.         cin>>t1;
  202.         cin>>t2;
  203.         sasiedzi[t1].push_back(t2);
  204.         sasiedzi[t2].push_back(t1);
  205.     }
  206.  
  207.     ///STWORZENIE TABLICY OJCOW I SYNOW
  208.     father[1] = 1;
  209.     make_Tree(1);
  210.     /*cout<<"FATHER"<<endl;
  211.     for(int i=1; i<=n; i++)
  212.         cout<<i<<": "<<father[i]<<endl;*/
  213.  
  214.  
  215.     for(int i=1; i<=n; i++)
  216.         roz[i] = -1;
  217.  
  218.     make_Roz(1);
  219.     ///STWORZENIE TABLICY PREORDER
  220.     make_Preorder(1);
  221.    /* cout<<endl;
  222.     cout<<"PREORDER"<<endl;
  223.     for(int i=1; i<=n; i++)
  224.         cout<<i<<": "<<preorder[i]<<endl;*/
  225.  
  226.     ///STWORZENIE DRZEWA PRZEDZIALOWEGO i obliczenie ZAKRESOW dla wierzcholkow
  227.     while(max_pot<n)
  228.         max_pot*=2;
  229.     //cout<<"max_pot: "<<max_pot<<endl;
  230.  
  231.     for(int i=max_pot; i<2*max_pot; i++)
  232.     {przedz_seg_tree[i].first = i-max_pot+1;
  233.      przedz_seg_tree[i].second = i-max_pot+1; }
  234.  
  235.     for(int i=max_pot-1; i>=1; i--)
  236.     {
  237.         przedz_seg_tree[i].first = przedz_seg_tree[2*i].first;
  238.         przedz_seg_tree[i].second = przedz_seg_tree[2*i+1].second;
  239.     }
  240.     /*cout<<endl;
  241.     cout<<"ZAKRESY"<<endl;
  242.     for(int i=1; i<2*max_pot; i++)
  243.         cout<<i<<": "<<przedz_seg_tree[i].first<<"   "<<przedz_seg_tree[i].second<<endl;
  244.  
  245.  
  246.     cout<<endl;
  247.     cout<<"ROZ"<<endl;
  248.     for(int i=1; i<2*max_pot; i++)
  249.         cout<<i<<": "<<roz[i]<<endl;*/
  250.     for(int i=0; i<=n; i++)
  251.         uzyteczne[i] = true;
  252.  
  253.  
  254.     int q;
  255.     cin>>q;
  256.     char ct1;
  257.     int tem2;
  258.     int t3;
  259.     for(int i=0; i<q; i++)
  260.     {
  261.  
  262.         cin>>ct1;
  263.         cin>>tem2;
  264.         if(ct1 == '?')
  265.         {cin>>t3; Ans(tem2, t3);}
  266.         else if(ct1 == '+')
  267.             Add(tem2);
  268.         else
  269.             Divide(tem2);
  270.  
  271.        // cout<<"DRZEWO PO ZMIANACH"<<endl;
  272.         //for(int i=1; i<2*max_pot; i++)
  273.           //  cout<<i<<": "<<seg_tree[i].first<<"   "<<seg_tree[i].second<<endl;
  274.  
  275.     }
  276.  
  277.  
  278.  
  279.     return 0;
  280. }
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