daily pastebin goal
73%
SHARE
TWEET

Untitled

a guest Jan 19th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <list>
  3. #include <queue>
  4. #include <stack>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9. bool win=false;
  10. bool remis=false;
  11. bool remis2=false;
  12. struct wezel
  13. {
  14.     int i;
  15.     vector <int> sasiedzi;
  16.     bool czer=0;
  17.     bool ziel=0;
  18.     int drogaczer;
  19.     int drogaziel;
  20. };
  21. void bfs(queue<int> &qg, queue<int>&qr,int i, wezel tab[])
  22. {
  23.     int wsk;
  24. while(qg.size()!=0 || qr.size()!=0)
  25. {
  26.     if(qg.size()!=0)
  27.     {
  28.  
  29.         while(qg.size()!=0)
  30.         {
  31.  
  32.             wsk=qg.front();
  33.             qg.pop();
  34.             vector<int>::iterator it;
  35.             int wskk;
  36.             if(tab[wsk].sasiedzi.size()==0&& tab[wsk].ziel==true)
  37.             {
  38.                 cout << "TAK"<< "\n";
  39.                 win=true;
  40.                 stack<int> s;
  41.                 while(i!=0)
  42.                 {
  43.                     if(i==0)
  44.                         break;
  45.                     s.push(wsk);
  46.                     wsk=tab[wsk].drogaczer;
  47.                     i--;
  48.                     if(i==0)
  49.                         break;
  50.                     s.push(wsk);
  51.                     wsk=tab[wsk].drogaziel;
  52.                     i--;
  53.                 }
  54.                 while(s.size()!=0)
  55.                 {
  56.                     cout<<s.top() << " ";
  57.                     s.pop();
  58.                 }
  59.               cout<<"\n";
  60.                 return;
  61.             }
  62.             else if(tab[wsk].sasiedzi.size()!=0)
  63.             {
  64.                 sort(tab[wsk].sasiedzi.begin(), tab[wsk].sasiedzi.end());
  65.                 remis2=true;
  66.                 for(it=tab[wsk].sasiedzi.begin(); it!=tab[wsk].sasiedzi.end(); ++it)
  67.                 {
  68.  
  69.                     wskk=*it;
  70.                     if(tab[wskk].czer && tab[wsk].ziel)
  71.                     {
  72.                         remis=true;
  73.                     }
  74.                     if(tab[wskk].czer==false && tab[wsk].ziel)
  75.                     {
  76.                         tab[wskk].czer=true;
  77.                         tab[wskk].drogaziel=wsk;
  78.                         qr.push(wskk);
  79.                     }
  80.                 }
  81.             }
  82.         }
  83.         i++;
  84.     }
  85.     else
  86.     {
  87.         while(qr.size()!=0)
  88.         {
  89.  
  90.             wsk=qr.front();
  91.             qr.pop();
  92.             vector<int>::iterator it;
  93.             int wskk;
  94.             if(tab[wsk].sasiedzi.size()!=0)
  95.             {
  96.                 sort(tab[wsk].sasiedzi.begin(), tab[wsk].sasiedzi.end());
  97.                 remis2=true;
  98.                 for(it=tab[wsk].sasiedzi.begin(); it!=tab[wsk].sasiedzi.end(); ++it)
  99.                 {
  100.                     wskk=*it;
  101.                     if(tab[wskk].ziel && tab[wsk].czer)
  102.                     {
  103.                         remis=true;
  104.                     }
  105.  
  106.                     if(tab[wskk].ziel==false && tab[wsk].czer)
  107.                     {
  108.  
  109.                         tab[wskk].ziel=true;
  110.                         tab[wskk].drogaczer=wsk;
  111.                         qg.push(wskk);
  112.                     }
  113.                 }
  114.             }
  115.  
  116.         }
  117.         i++;
  118.     }
  119. }
  120. }
  121. int main()
  122. {
  123.     ios_base::sync_with_stdio(false);
  124.     int p;
  125.     cin >> p;
  126.     for(int i =0; i<p; i++ )
  127.     {
  128.         int k;
  129.         int m;
  130.         int poz;
  131.         cin >> k >> m >> poz;
  132.         wezel tab[k];
  133.        // wezel **tab= new wezel*[k];
  134.         for(int b=0; b<k; b++)
  135.         {
  136.                         // to przekracza pamięć
  137.               tab[b].i=b;
  138.         }
  139.  
  140.         int a,b;
  141.         for(int j=0; j<m; j++)
  142.         {
  143.             cin >> a >> b;
  144.             tab[a].sasiedzi.push_back(b);
  145.         }
  146.         queue <int> qg;
  147.         tab[poz].ziel=true;
  148.         qg.push(poz);
  149.         queue <int> qr;
  150.         bfs(qg,qr,1,tab);
  151.         if(!win && (remis || !remis2))
  152.             cout << "REMIS"<<"\n";
  153.         else if(!win)
  154.             cout << "NIE"<< "\n";
  155.         win=false;
  156.         remis=false;
  157.         remis2=false;
  158.     }
  159. }
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