fork download
copy 
  1. #pragma GCC optimize(2)
  2. #pragma GCC optimize(3)
  3. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
  4. #pragma GCC target("avx,avx2,fma")
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9. #define DEBUG(x) cout << '>' << #x << ':' << x << endl;
  10. #define loop(i,n) for(ll i=0;i<(n);i++)
  11. #define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
  12. #define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
  13. #define cases ll T=0;cin>>T;while(T--)
  14. #define ff first
  15. #define ss second
  16. #define all(v) v.begin(),v.end()
  17. #define END "\n"
  18. #define pb push_back
  19. #define go(c,itr) for(auto itr=(c).begin(); itr!=(c).end(); itr++)
  20. #define back(c,itr) for(auto itr=(c).rbegin(); itr!=(c).rend(); itr++)
  21. #define inf 9e18
  22. #define MOD 1000000007
  23. #define MODU 998244353
  24. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  25. #define MAXN 200001
  26. const string alpha = "abcdefghijklmnopqrstuvwxyz";
  27. vector<ll> adj[26];
  28. vector<ll> topsort, indegree(26);
  29. unordered_map<ll, ll> flag;
  30. void kahn(ll n)
  31. {
  32. 	priority_queue<ll> q;
  33. 	ll ctr = 0;
  34. 	FOR(i, 0, n - 1)
  35. 	{
  36. 		if (indegree[i] == 0 && flag[i] == 1)
  37. 			q.push(i);
  38. 		if (flag[i] == 1)
  39. 			++ctr;
  40. 	}
  41. 	while (!q.empty())
  42. 	{
  43. 		ll node = q.top();
  44. 		q.pop();
  45. 		topsort.pb(node);
  46. 		for (auto child : adj[node])
  47. 		{
  48. 			--indegree[child];
  49. 			if (indegree[child] == 0)
  50. 				q.push(child);
  51. 		}
  52. 	}
  53. 	if (topsort.size() != ctr)
  54. 		cout << "-1";
  55. 	else
  56. 		for (auto itr : topsort)
  57. 			cout << char(itr + 65);
  58. 	cout << END;
  59. }
  60.  
  61. signed main() {
  62. // #ifndef ONLINE_JUDGE
  63. // 	freopen("input.txt", "r", stdin);
  64. // 	freopen("output.txt", "w", stdout);
  65. // #endif
  66. 	fast
  67. 	ll t;
  68. 	cin >> t;
  69. 	FOR(x, 1, t)
  70. 	{
  71. 		ll r, c;
  72. 		cin >> r >> c;
  73. 		vector<vector<char>> a(r, vector<char>(c));
  74. 		loop(i, r)
  75. 		{
  76. 			loop(j, c)
  77. 			{
  78. 				cin >> a[i][j];
  79. 			}
  80. 		}
  81. 		if (r == 1)
  82. 		{
  83. 			cout << "Case #" << x << ": ";
  84. 			set<char> ch;
  85. 			loop(i, r)
  86. 			loop(j, c)
  87. 			ch.insert(a[i][j]);
  88. 			go(ch, itr)	cout << *itr;
  89. 			cout << END;
  90. 		}
  91. 		else
  92. 		{
  93. 			unordered_map<ll, ll> fl[26];
  94. 			loop(i, 26)
  95. 			{
  96. 				loop(j, c)
  97. 				{
  98. 					loop(k, r - 1)
  99. 					{
  100. 						if (a[k][j] == char(i + 65))
  101. 						{
  102. 							if (a[k + 1][j] != char(i + 65) && fl[(ll(a[k + 1][j]) - 65)][i] == 0)
  103. 							{
  104. 								adj[(ll(a[k + 1][j]) - 65)].pb(i);
  105. 								++indegree[i];
  106. 								fl[(ll(a[k + 1][j]) - 65)][i] = 1;
  107. 							}
  108. 						}
  109. 						flag[ll(a[k][j]) - 65] = flag[ll(a[k + 1][j]) - 65] = 1;
  110. 					}
  111. 				}
  112. 			}
  113. 			// loop(i, 26)
  114. 			// {
  115. 			// 	if (flag[i])
  116. 			// 	{
  117. 			// 		cout << char(i + 65) << " : ";
  118. 			// 		go(adj[i], itr)
  119. 			// 		{
  120. 			// 			cout << char(*itr + 65) << " ";
  121. 			// 		}
  122. 			// 		cout << END;
  123. 			// 	}
  124. 			// }
  125. 			cout << "Case #" << x << ": "; kahn(26);
  126. 			loop(i, 26)
  127. 			{
  128. 				indegree[i] = 0;
  129. 				adj[i].clear();
  130. 				fl[i].clear();
  131. 			}
  132. 			topsort.clear();
  133. 			flag.clear();
  134. 		}
  135. 	}
  136. 	return 0;
  137. }
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
4
4 6
ZOAAMM
ZOAOMM
ZOOOOM
ZZZZOM
4 4
XXOO
XFFO
XFXO
XXXO
5 3
XXX
XPX
XXX
XJX
XXX
3 10
AAABBCCDDE
AABBCCDDEE
AABBCCDDEE
stdout
copy 
Case #1: ZOMA
Case #2: -1
Case #3: -1
Case #4: EDCBA
https://ideone.com/TUerfZ
language:
C++14 (clang 8.0)
created:
3 years ago
visibility:
secret

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!