fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <string>
  6. #include <cstring>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <set>
  11. #include <map>
  12. #include <cstdlib>
  13. #include <iomanip>
  14. #include <ctime>
  15. #include <utility>
  16.  
  17. #define x first
  18. #define y second
  19. #define mp make_pair
  20. #define pb push_back
  21. #define sqr(x) (x)*(x)
  22. #define _with_file
  23. #define TASK ""
  24. #define forn(i, n) for(int i = 0; i < (int)n; ++i)
  25.  
  26. void quit(); 
  27.  
  28. using namespace std;
  29.  
  30. typedef long long i64;
  31. typedef unsigned long long u64;
  32. typedef long double ld;
  33. typedef pair <int, int> PII;
  34. typedef pair <i64, i64> PII64;
  35. typedef pair <ld, ld> PLL;
  36.  
  37. const ld PI = acos(-1);
  38. const ld EPS = 1e-10;
  39. double __t;
  40.  
  41.  
  42. int val(char c)
  43. {
  44.     if (c >= '0' && c <= '9')
  45.         return c - '0';
  46.     if (c >= 'a' && c <= 'z')
  47.         return c - 'a' + 10;
  48.     if (c >= 'A' && c <= 'Z')
  49.         return c - 'A' + 36;
  50. }
  51.  
  52. char symb(int x)
  53. {
  54.     if (x < 10)
  55.         return x + '0';
  56.     if (x < 36)
  57.         return x + 'a' - 10;
  58.     return x + 'A' - 36; 
  59. }
  60.  
  61. int toi(char c1, char c2)
  62. {
  63.     return val(c1)*62 + val(c2); 
  64. }
  65.  
  66. string tos(int x)
  67. {
  68.     string res = "";
  69.     res += symb(x/62);
  70.     res += symb(x%62);
  71.     return res;
  72. }
  73.  
  74. int n;
  75.  
  76. vector <int> g[4000];
  77. int p[4000];
  78. bool u1[4000];
  79. bool u2[4000];
  80. vector <int> ans;
  81.  
  82. void dfs(int v)
  83. {
  84.     u2[v] = 1;
  85.     while(p[v] < (int)g[v].size())
  86.         dfs(g[v][p[v]++]);
  87.     ans.pb(v);
  88. }
  89.  
  90. int in[4000];
  91. int out[4000];
  92.  
  93. int bc, ec;
  94. int b, e;
  95.  
  96. int main()
  97. {
  98.     #ifdef local
  99.         __t = clock();
  100.         #ifndef _with_files
  101.             freopen("z.in", "rt", stdin);
  102.             freopen("z.out", "wt", stdout);
  103.         #endif
  104.     #endif
  105.     #ifdef _with_files
  106.         freopen(TASK".in", "rt", stdin);
  107.         freopen(TASK".out", "wt", stdout);
  108.     #endif
  109.     cin >> n;
  110.     string s;
  111.     b = -1;
  112.     for(int i = 0; i < n; ++i)
  113.     {
  114.         cin >> s;
  115.         g[toi(s[0], s[1])].pb(toi(s[1], s[2]));
  116.         u1[toi(s[0], s[1])] = 1;
  117.         u1[toi(s[1], s[2])] = 1;
  118.     }
  119.     for(int i = 0; i < 4000; ++i)
  120.     {
  121.         out[i] = g[i].size();
  122.         for(int j = 0; j < (int)g[i].size(); ++j)
  123.             in[g[i][j]]++;
  124.     }
  125.     for(int i = 0; i < 4000; ++i)
  126.     {
  127.         if (u1[i])
  128.         {
  129.             if (in[i] == out[i] + 1)
  130.             {
  131.                 e = i;
  132.                 ec++;
  133.             } else
  134.             {
  135.                 if (in[i] == out[i] - 1)
  136.                 {
  137.                     b = i;
  138.                     bc++;
  139.                 }
  140.                 else
  141.                 {
  142.                     if (in[i] != out[i])
  143.                     {
  144.                         cout << "NO";
  145.                         quit();
  146.                     }
  147.                 }
  148.             }
  149.         }
  150.     }
  151.     if (!((bc == 1 && ec == 1) || (bc == 0 && ec == 0)))
  152.     {
  153.         cout << "NO";
  154.         quit();
  155.     }
  156.     if (b == -1)
  157.     {
  158.         for(int i = 0; i < 4000; ++i)
  159.         {
  160.             if (u1[i])
  161.             {
  162.                 b = i;
  163.                 break;
  164.             }   
  165.         }
  166.     }    
  167.     dfs(b);
  168.     for(int i = 0; i < 4000; ++i)
  169.     {
  170.         if (u1[i] != u2[i])
  171.         {
  172.             cout << "NO";
  173.             quit();
  174.         }
  175.     }  
  176.     reverse(ans.begin(), ans.end());
  177.     cout << "YES\n";
  178.     cout << tos(ans[0])[0];
  179.     for(int i = 1; i < (int)ans.size()-1; ++i)
  180.         cout << tos(ans[i])[0]; 
  181.     cout << tos(ans.back());
  182.     quit();
  183. }
  184.  
  185. void quit()
  186. {
  187.     #ifdef local
  188.         cerr << "\nTOTAL TIME: "<< (clock() - __t)/1000.0 << " s\n";
  189.     #endif
  190.     exit(0);        
  191. }
  192.  
Success #stdin #stdout 0s 3336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
00/
https://ideone.com/P5xzvG
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!