結果
問題 | No.517 壊れたアクセサリー |
ユーザー |
![]() |
提出日時 | 2017-05-28 22:13:53 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,154 bytes |
コンパイル時間 | 882 ms |
コンパイル使用メモリ | 94,164 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-21 15:31:44 |
合計ジャッジ時間 | 1,572 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:95:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 95 | scanf("%d",&n); | ~~~~~^~~~~~~~~ main.cpp:98:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 98 | scanf("%s",s); | ~~~~~^~~~~~~~
ソースコード
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <functional> #include <cassert> typedef long long ll; using namespace std; #define debug(x) cerr << #x << " = " << (x) << endl; #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 100010 /* TopologicalSort */ vector<int> TopologicalSort(vector<vector<int> > G,int n= -1){ if(n==-1) n=(int)G.size(); int u; vector<int> ret,ret2; queue<int> que; vector<int> indeg(n+1,0); for(int i=0;i<n;i++){ for(int j=0;j<G[i].size();j++){ indeg[G[i][j]]++; } } for(int i=0;i<n;i++){ if(indeg[i]==0){ que.push(i); } } while(!que.empty()){ u = que.front(); que.pop(); ret.push_back(u); for(int i=0;i<G[u].size();i++){ indeg[G[u][i]]--; if(indeg[G[u][i]]==0){ que.push(G[u][i]); } } } if(n==(int)ret.size()){ return ret; }else{ return ret2; } } bool f[26] = {}; bool check(vector<vector<int> > way, int i, int j, string s){ way[i].push_back(j); auto res = TopologicalSort(way,26); if(res.size()){ return true; } return false; } int main(){ vector<vector<int> > way(26, vector<int>()); for(int i=0;i<2;i++){ int n; char s[40]; scanf("%d",&n); for(int j=0;j<n;j++){ scanf("%s",s); for(int k=0;s[k]!='\0';k++) f[s[k]-'A'] = true; for(int k=1;s[k]!='\0';k++){ way[s[k-1]-'A'].push_back(s[k]-'A'); } } } auto ans = TopologicalSort(way, 26); if(ans.size() == 0){ puts("-1"); return 0; } string ans_s = ""; for(int i=0;i<ans.size();i++){ if(f[ans[i]]) ans_s += 'A' + ans[i]; } for(int i=0;i<ans_s.size();i++){ for(int j=i+1;j<ans_s.size();j++){ if(check(way, ans_s[j]-'A', ans_s[i]-'A', ans_s)){ puts("-1"); return 0; } } } cout << ans_s << endl; return 0; }