Advertisement
jedrzejd

Untitled

Sep 23rd, 2017
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cmath>
  6. #include <string>
  7. #define wejscie first
  8. #define wyjscie second
  9. using namespace std;
  10. const int m=1000005;
  11. int odwiedzone[m];
  12. string t,pom,pom1;
  13. vector<pair<int,char> >tab[m];
  14. int tablica[m];
  15. int costam=0;
  16. vector<int>wynik;
  17. pair<int,int>stopien[m];
  18. int converter(string tab){
  19.     int index=int(tab[0])*500+int(tab[1]);
  20.     return index;
  21. }
  22. string zamiana(int tab){
  23.     string ad="";
  24.     ad+=char(tab/500);
  25.     ad+=char(tab%500);
  26.     return ad;
  27. }
  28. void dfs(int v){
  29.     while(!tab[v].empty()){
  30.         costam++;
  31.         int w=tab[v].back().first;
  32.         wynik.push_back(tab[v].back().second);
  33.         tab[v].pop_back();
  34.         dfs(w);
  35.     }
  36. }
  37. int main(){
  38.     int n;
  39.     scanf("%d",&n);
  40.     int ile=0;
  41.     for(int i=0;i<n;++i){
  42.         cin>>t;
  43.         pom="";
  44.         pom1="";
  45.         pom+=t[0];
  46.         pom+=t[1];
  47.         pom1+=t[1];
  48.         pom1+=t[2];
  49.         int a=0,b=0;
  50.         a=(converter(pom));
  51.         b=(converter(pom1));
  52.         tab[a].push_back(make_pair(b,t[2]));
  53.         stopien[a].wyjscie++;
  54.         stopien[b].wejscie++;
  55.     }
  56.     int czy=0,czy1=0;
  57.     int start=-1,start1=-1;
  58.     for(int i=0;i<=1000000;++i){
  59.         if(stopien[i].wejscie==stopien[i].wyjscie&&stopien[i].wejscie>0){
  60.             start1=i;
  61.             ile++;
  62.         }
  63.         else if(stopien[i].wyjscie-stopien[i].wejscie==1){
  64.             start=i;
  65.             czy1++;
  66.         }
  67.         else if(stopien[i].wejscie-stopien[i].wyjscie==1){
  68.             czy++;
  69.         }
  70.     }
  71.     //printf("%d %d %d %d\n",czy,czy1,start,start1);
  72.     if(czy1==1&&czy==1){
  73.         string pom=zamiana(start);
  74.         wynik.push_back(pom[0]);
  75.         wynik.push_back(pom[1]);
  76.         dfs(start);
  77.         if(costam!=n||wynik.size()!=(n+2)){
  78.             printf("-1\n");
  79.         }
  80.         else {
  81.             for(int i=0;i<wynik.size();++i){
  82.                 printf("%c",wynik[i]);
  83.             }
  84.         }
  85.     }
  86.     else if(czy==0&&czy1==0){
  87.         string pom=zamiana(start1);
  88.         wynik.push_back(pom[0]);
  89.         wynik.push_back(pom[1]);
  90.         dfs(start1);
  91.         if(costam!=n||wynik.size()!=(n+2)){
  92.             printf("-1\n");
  93.         }
  94.         else {
  95.             for(int i=0;i<wynik.size();++i){
  96.                 printf("%c",wynik[i]);
  97.             }
  98.         }
  99.     }
  100.     else {
  101.         printf("-1\n");
  102.     }
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement