結果
問題 | No.517 壊れたアクセサリー |
ユーザー |
![]() |
提出日時 | 2017-05-28 21:45:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 1,554 ms |
コンパイル使用メモリ | 172,892 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 15:21:58 |
合計ジャッジ時間 | 2,216 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++) template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; } template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; } typedef long long ll; int N,M; bool edge [26] [26]; bool have [26]; int main() { scanf("%d",&N); vector<string> S(N); vector<int> indeg(26),outdeg(26); FOR(i,0,N){ cin >> S [i]; FOR(j,0,S [i].size()) have [S [i] [j] - 'A'] = true; FOR(j,1,S [i].size()){ int u = S [i] [j - 1] - 'A',v = S [i] [j] - 'A'; if(edge [u] [v] == false){ edge [u] [v] = true; outdeg [u]++; indeg [v]++; } } } scanf("%d",&M); vector<string> T(M); FOR(i,0,M){ cin >> T [i]; FOR(j,1,T [i].size()){ int u = T [i] [j - 1] - 'A',v = T [i] [j] - 'A'; if(edge [u] [v] == false){ edge [u] [v] = true; outdeg [u]++; indeg [v]++; } } } FOR(i,0,26) if(indeg [i] >= 2 || outdeg [i] >= 2){ puts("-1"); return 0; } int K = accumulate(have,have + 26,0); string ans; while(ans.size() < K){ bool flag = true; vector<int> v; FOR(i,0,26) if(have [i] && indeg [i] == 0){ v.push_back(i); have [i] = false; } if(v.size() == 1){ ans += char('A' + v.front()); FOR(i,0,26) if(edge [v.front()] [i]){ indeg [i]--; } } else{ puts("-1"); return 0; } } cout << ans << endl; return 0; }