YEZAELP

KOI06: Cecil

Dec 7th, 2021 (edited)
521
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e2 + 10;
  5. const int AZ = 26;
  6. string str[N];
  7. int len[N], indeg[N];
  8. vector <int> g[AZ + 10];
  9. bool inpath[AZ + 10];
  10.  
  11. int to_int(char a){
  12.     return a - 'a' + 1;
  13. }
  14.  
  15. char to_char(int a){
  16.     return a + 'a' - 1;
  17. }
  18.  
  19. int main(){
  20.  
  21.     int n;
  22.     scanf("%d", &n);
  23.  
  24.     for(int i=1;i<=n;i++){
  25.         cin >> str[i];
  26.         len[i] = str[i].size();
  27.         if(i == 1) continue;
  28.         int pre = 0, cur = 0;
  29.         while(pre < len[i - 1] and cur < len[i] and str[i - 1][pre] == str[i][cur]){
  30.             pre ++, cur ++;
  31.         }
  32.         if(pre < len[i - 1] and cur < len[i]) g[to_int(str[i - 1][pre])].push_back(to_int(str[i][cur]));
  33.     }
  34.  
  35.     for(int u=1;u<=AZ;u++){
  36.         if(g[u].empty()) continue;
  37.         for(auto v: g[u]){
  38.             indeg[v] ++;
  39.             inpath[v] = true;
  40.         }
  41.     }
  42.  
  43.     priority_queue <int, vector <int>, greater <int>> q;
  44.     for(int i=1;i<=AZ;i++)
  45.         if(indeg[i] == 0) q.push(i);
  46.     vector <int> seq;
  47.     while(!q.empty()){
  48.         int u = q.top(); q.pop();
  49.         seq.push_back(u);
  50.         for(auto v: g[u]){
  51.             indeg[v] --;
  52.             if(indeg[v] == 0) q.push(v);
  53.         }
  54.     }
  55.  
  56.     if(seq.size() < 26) printf("-1");
  57.     else{
  58.         for(auto s: seq) printf("%c", to_char(s));
  59.     }
  60.  
  61.     return 0;
  62. }
RAW Paste Data