fork download
copy 
  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. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  7. #define ll long long int
  8. #define ull unsigned long long int
  9. #define ld long double
  10. #define endl '\n'
  11. #define loop(a,b,c) for(ll i=a;i<=b;i+=c)
  12. #define intarr(arr,n) ll arr[n];for(ll i=0;i<n;i++)cin>>arr[i]
  13. #define inparr(arr,n) for(ll i=0;i<n;i++)cin>>arr[i]
  14. #define inpvec(vec,n) for(ll i=0;i<n;i++){ll var;cin>>var;vec.push_back(var);}
  15. #define pb push_back
  16. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
  17. #define mod 1000000007
  18. #define newline cout<<endl
  19. #define ump unordered_map<ll,ll>
  20. #define vec vector<ll>
  21. #define mkp make_pair
  22. #define disp(var1,var2) cout<<var1<<" "<<var2<<endl;
  23. #define all(v)             v.begin(),v.end()
  24. #define cout(var) cout<<var<<endl
  25. #define mod2 998244353
  26. #define fbo find_by_order  /// find kth smallest by passing k-1
  27. #define ook order_of_key  //// find no of smaller items less than k
  28. #define teensort(a,r,g,b) a[0]=r;a[1]=g;a[2]=b;sort(a,a+3);
  29. #define ss second
  30. #define ff first
  31. #define displayarray(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "; cout<<endl;
  32. #define pi pair<ll,ll>
  33. #define meramax 1e18
  34. #define meramin -1e18
  35. #define percentile 1000000007
  36. #define PI 3.14159265358979323846
  37.  
  38. vector<string> v;
  39. void bfs(auto g)
  40. {
  41.     string str="";
  42.     string ans="";
  43.     auto *visited = new bool[28]; 
  44.     for(ll i=0;i<28;i++) 
  45.         visited[i] = false; 
  46.     list<ll> queue; 
  47.     visited[27] = true; 
  48.     queue.push_back(27); 
  49.     str+="27";
  50.     list<ll>::iterator i; 
  51.     while(!queue.empty()) 
  52.     { 
  53.         auto s = queue.front();
  54.         if(s==27)
  55.         {
  56.             str+="27";
  57.         }
  58.         else
  59.         {
  60.             char ch='A'+s; 
  61.             str+=ch;
  62.         }
  63.         queue.pop_front(); 
  64.         for (i = g[s].begin(); i != g[s].end(); ++i) 
  65.         { 
  66.             if (!visited[*i]) 
  67.             { 
  68.                 visited[*i] = true; 
  69.                 queue.push_back(*i); 
  70.             } 
  71.         } 
  72.     } 
  73.     for(ll i=0;i<str.length();)
  74.     {
  75.         if(i+1<str.length() && str[i]=='2' && str[i+1]=='7')
  76.         {
  77.             i+=2;
  78.             continue;
  79.         }
  80.         else
  81.         {
  82.             ans+=str[i];
  83.             i++;
  84.         }
  85.     }
  86.     v.pb(ans);
  87.     //cout(ans);
  88.     return;
  89. }
  90. void AcDegaYe()
  91. {
  92.     ll r,c;
  93.     cin>>r>>c;
  94.     char a[r+1][c+1];
  95.     unordered_map<char,ll> h;
  96.     for(ll i=1;i<=r;i++)
  97.     {
  98.         for(ll j=1;j<=c;j++)
  99.         {
  100.             cin>>a[i][j];
  101.             h[a[i][j]]++;
  102.         }
  103.     }
  104.     ll neeche[26];
  105.     for(ll i=0;i<26;i++)neeche[i]=27;
  106.     for(ll i=1;i<=r-1;i++)
  107.     {
  108.         for(ll j=1;j<=c;j++)
  109.         {
  110.             if(a[i][j]!=a[i+1][j])
  111.             {
  112.                 neeche[a[i][j]-'A']=a[i+1][j]-'A';
  113.             }
  114.         }
  115.     }
  116.     unordered_map<ll,list<ll>> g;
  117.     ll f=0;
  118.     for(ll i=0;i<26;i++)
  119.     {
  120.         char ch='A'+i;
  121.         if(h.count(ch)==1)
  122.         {
  123.             if(neeche[neeche[i]]==i)
  124.             {
  125.                 f=1;
  126.                 break;
  127.             }
  128.             g[i].pb(neeche[i]);
  129.             g[neeche[i]].pb(i);
  130.         }
  131.     }
  132.     if(f)
  133.     {
  134.         v.pb("-1");
  135.     }
  136.     else
  137.     {
  138.         bfs(g);
  139.     }
  140. }
  141. int main()
  142. {   
  143.  
  144.     fastio
  145.     ll t;
  146.     cin>>t;
  147.     //ll t=1;
  148.     while(t--)
  149.     {
  150.         AcDegaYe();
  151.     }
  152.     for(ll i=1;i<=v.size();i++)
  153.     {
  154.         cout<<"Case #"<<i<<": "<<v[i-1]<<endl;
  155.     }
  156.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  157.     return 0;
  158. }
Time limit exceeded #stdin #stdout 5s 920676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u8gzBD
language:
C++14 (gcc 8.3)
created:
3 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!