fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define debug(x) cout<<x<<"DE\n";
  6. #define debug2(x,y) cout<<x<<" "<<y<<"DE\n";
  7.  
  8.  
  9.  
  10. int main()
  11. {
  12.     ll t=1,ca=1,t2;
  13.     cin>>t;t2=t;
  14.     while(t--){
  15.         ll n;
  16.         string s,s2;
  17.         cin>>s;
  18.         s2=s;
  19.         n=s.size();
  20.         ll m;
  21.         cin>>m;
  22.         vector<char>ch[26];
  23.         for(int i=0;i<26;i++)ch[i].clear();
  24.         for(int i=1;i<=m;i++){
  25.             char u,v;
  26.             cin>>u>>v;
  27.             ch[u-'a'].push_back(v);
  28.         }
  29.         for(int i=0;i<26;i++){
  30.             sort(ch[i].begin(),ch[i].end());
  31.         }
  32.  
  33.         ll zzz=1,ok=1;
  34.         for(int i=0;i<n;i++){
  35.             if(i==0){
  36.                 while(1){
  37.                     ll a=s[i]-'a';
  38.                     if(ch[a].size()==0)break;
  39.                     for(int j=0;j<ch[a].size();j++){
  40.                         if(ch[a][j]<s[i]){
  41.                             s[i]=ch[a][j];break;
  42.                         }
  43.                     }
  44.                     ll z4=s[i]-'a';
  45.                     if(z4==a)break;
  46.                 }
  47.             }
  48.             else{
  49.                 ll b=s[i-1]-'a';
  50.                 ll a=s[i]-'a';
  51.                 if(b>a){zzz=0;
  52.                     while(1){
  53.                         a=s[i]-'a';
  54.                         if(ch[a].size()==0)break;
  55.                         else if(b<=a){
  56.                             while(1){
  57.                         a=s[i]-'a';
  58.                         if(ch[a].size()==0)break;
  59.                         for(int j=0;j<ch[a].size();j++){
  60.                             if(ch[a][j]<s[i]&&ch[a][j]>=s[i-1]){
  61.                                 s[i]=ch[a][j];break;
  62.                             }
  63.                         }
  64.                         ll z4=s[i]-'a';
  65.                         if(z4==a)break;
  66.                     }
  67.                         }
  68.                         for(int j=0;j<ch[a].size();j++){
  69.                             if(ch[a][j]>=s[i-1]){
  70.                                 zzz=1,s[i]=ch[a][j];break;
  71.                             }
  72.                         }
  73.                         ll z4=s[i]-'a';
  74.                         if(z4==a)break;
  75.                     }
  76.  
  77.                 }
  78.                 else if(a>b){
  79.                     while(1){
  80.                         a=s[i]-'a';
  81.                         if(ch[a].size()==0)break;
  82.                         for(int j=0;j<ch[a].size();j++){
  83.                             if(ch[a][j]<s[i]&&ch[a][j]>=s[i-1]){
  84.                                 s[i]=ch[a][j];break;
  85.                             }
  86.                         }
  87.                         ll z4=s[i]-'a';
  88.                         if(z4==a)break;
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.  
  94.         ok=1;
  95.         for(int i=1;i<n;i++){
  96.             if(s[i]<s[i-1]){ok=0;break;}
  97.         }
  98.  
  99.         if(ok)cout<<"YES\n";
  100.         else cout<<"NO\n";
  101.  
  102.     }
  103. }
  104.  
Success #stdin #stdout 0s 4648KB
comments (?)
stdin 
Standard input is empty
stdout 
YES
https://ideone.com/fbCXo6
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!