Guest User

WORDS1

a guest
Aug 13th, 2020
42
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. #define     bit_1(a)       __builtin_popcount(a)
  8. #define     ull            unsigned long long
  9. #define     ll             long long
  10. #define     pb             push_back
  11. #define     pf             push_front
  12. #define     mpr            make_pair
  13. #define     ins            insert
  14. #define     ff             first
  15. #define     ss             second
  16. #define     vi             vector<int>
  17. #define     vl             vector<ll>
  18. #define     vstr           vector<string>
  19. #define     si             set<int>
  20. #define     sl             set<ll>
  21. #define     li             list<int>
  22. #define     pii            pair<int,int>
  23. #define     pll            pair<ll,ll>
  24. #define     mii            map<int,int>
  25. #define     mll            map<ll,ll>
  26. #define     ma             INT_MAX
  27. #define     mi             INT_MIN
  28. #define     mod            1000000007
  29. #define     pi             3.14159265359
  30. #define     e              2.71828182846
  31. #define     inf            1000000000000000LL
  32. #define     all(x)         x.begin(), x.end()
  33. #define     lb(a,b,c)      lower_bound(a,a+b,c)-a
  34. #define     ub(a,b,c)      upper_bound(a,a+b,c)-a
  35. #define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
  36. #define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
  37. #define     srt1(a,b)      sort(a,a+b)
  38. #define     srt2(a,b)      sort(a,a+b,greater<int>())
  39. #define     gcd(a,b)       __gcd(a,b)
  40. #define     lcm(a,b)       (a*(b/gcd(a,b)))
  41. #define     harmonic(n)    0.57721566490153286l+log(n)
  42. #define     mem(a, b)      memset(a, b, sizeof(a))
  43. #define     orderset1      tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
  44. #define     orderset2      tree<int,null_type,greater<int>,rb_tree_tag,tree_order_statistics_node_update>
  45.  
  46. ///s.lower_bound(a),s.upper_bound(a), for set
  47. ///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
  48. ///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));
  49. /// lcm(a,b)=a/gcd(a,b)*b (handle overflow)
  50.  
  51. bool sortinrev1(const pair<int,int>&a,const pair<int,int>&b)
  52. {
  53.     //return (a.first > b.first);
  54.     if(a.first==b.first)return (a.second>b.second);
  55.     else return (a.first > b.first);
  56. }
  57. bool sortinrev2(const pair<int,int>&a,const pair<int,int>&b)
  58. {
  59.     //return (a.first > b.first);
  60.     if(a.first==b.first)return (a.second<b.second);
  61.     else return (a.first > b.first);
  62. }
  63. int fx[]={1,-1,0,0};
  64. int fy[]={0,0,1,-1};
  65.  
  66. vi adj[30];
  67. int in[30];
  68. int out[30];
  69. int visited[30];
  70. int alphabet[30];
  71.  
  72. void dfs(int node)
  73. {
  74.     visited[node]=true;
  75.     for(int i=0;i<adj[node].size();i++){
  76.         int child=adj[node][i];
  77.         if(!visited[child])dfs(child);
  78.     }
  79. }
  80.  
  81. int main()
  82. {
  83.     int t,n;
  84.     string str;
  85.     cin>>t;
  86.     while(t--){
  87.         cin>>n;
  88.         for(int i=0;i<26;i++)adj[i].clear();
  89.         mem(in, 0);
  90.         mem(out,0);
  91.         mem(alphabet,0);
  92.         mem(visited,false);
  93.         getchar();
  94.         while(n--){
  95.             cin>>str;
  96.             int len=str.size();
  97.             adj[str[0]-'a'].pb(str[len-1]-'a');
  98.             out[str[0]-'a']++;
  99.             in[str[len-1]-'a']++;
  100.         }
  101.         bool flag=true;
  102.         for(int i=0;i<26;i++){
  103.             if(abs(in[i]-out[i])>1){
  104.                 flag=false;
  105.                 break;
  106.             }
  107.         }
  108.         /*for(int i=0;i<26;i++)cout<<in[i]<<" ";
  109.         cout<<endl;
  110.         for(int i=0;i<26;i++)cout<<out[i]<<" ";
  111.         cout<<endl;*/
  112.         if(!flag){
  113.             cout<<"The door cannot be opened.\n";
  114.             continue;
  115.         }
  116.         for(int i=0;i<26;i++){
  117.             if(in[i]||out[i]){
  118.                 alphabet[i]=-1;
  119.             }
  120.         }
  121.         bool flag2=false;
  122.         for(int i=0;i<26;i++){
  123.             if(abs(in[i]-out[i])==1){
  124.                 flag2=true;
  125.                 dfs(i);
  126.                 break;
  127.             }
  128.         }
  129.         bool flag4=false;
  130.         if(!flag2){
  131.             for(int i=0;i<26;i++){
  132.                 if(out[i]){
  133.                     flag4=true;
  134.                     dfs(i);
  135.                     break;
  136.                 }
  137.             }
  138.         }
  139.         if(!flag2 && !flag4){
  140.             cout<<"The door cannot be opened.\n";
  141.             continue;
  142.         }
  143.         bool flag3=true;
  144.         for(int i=0;i<26;i++){
  145.             if(alphabet[i]==-1&&!visited[i]){
  146.                 flag3=false;
  147.                 break;
  148.             }
  149.         }
  150.         if(flag3)cout<<"Ordering is possible.\n";
  151.         else cout<<"The door cannot be opened.\n";
  152.     }
  153. }
  154.  
  155.  
RAW Paste Data