提出 #822736

---

ソースコード 拡げる

#include <algorithm>
#include <array>
#include <complex>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline bool valid(const int x, const int r) { return 0 <= x && x < r; }

void initIOStream() {
  ios::sync_with_stdio(false); // stdinなどと同期しない
  cin.tie(0); // cinの前にflushしない
  cout.setf(ios::fixed);
  cout.precision(10); // 四捨五入して指定桁数表示
}

int N;
vector<string> A;
vector<string> B;
vector<vector<int> > G;
vector<int> D;

int main() {
  initIOStream();

  cin >> N;
  A.resize(N);
  B.resize(N);
  for(int i = 0; i < N; ++i){
    cin >> A[i] >> B[i];
  }

  G = vector<vector<int> >(26, vector<int>());
  D = vector<int>(26, 0);
  for(int i = 0; i < N; ++i){
    bool f = false;
    for(int j = 0, size = min(A[i].size(), B[i].size()); j < size; ++j){
      if(A[i][j] != B[i][j]){
        G[A[i][j] - 'a'].emplace_back(B[i][j] - 'a');
        ++D[B[i][j] - 'a'];
        f = true;
        break;
      }
    }
    if(!f){
      cout << -1 << endl;
      return 0;
    }
  }

  string ans;
  vector<bool> used(26, false);
  // for(const auto& d : D) cout << d << " "; cout << endl;
  while(ans.size() < 26){
    int idx = -1;
    for(int i = 0; i < 26; ++i){
      if(used[i]) continue;
      if(!D[i]){
        idx = i;
        break;
      }
    }
    if(idx == -1){
      ans = "-1";
      break;
    }
    ans.push_back('a' + idx);
    used[idx] = true;
    for(int i = 0, size = G[idx].size(); i < size; ++i){
      --D[G[idx][i]];
    }
  }
  cout << ans << endl;
}

提出情報

ジャッジ結果