fork(2) download
copy 
  1. /**
  2. 	Template by Akikaze (秋風) - formerly proptit_4t41.
  3. 	Code written by a random fan of momocashew and Chiho.
  4. **/
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. /** -----BASIC MACROES----- **/
  10. #define endl '\n'
  11. #define i64 long long
  12. #define ld long double
  13. #define pub push_back
  14. #define mp make_pair
  15. #define fi first
  16. #define se second
  17. const long long MOD = 1000000007LL, INF = 1e9, LINF = 1e18;
  18. const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
  19. typedef vector<i64> vi;
  20. typedef vector<ld> vd;
  21. typedef vector<string> vs;
  22. typedef vector<bool> vb;
  23. typedef pair<i64, i64> pii;
  24. typedef pair<i64, pii> pip;
  25. typedef pair<pii, i64> ppi;
  26.  
  27. /** -----BIT CONTROLS----- **/
  28. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  29. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  30. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  31. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  32.  
  33. /** -----IDEAS/ALGORITHMS-----
  34.  
  35.     -------------------------- **/
  36.  
  37. /** -----CUSTOM TYPEDEFS/DEFINES----- **/
  38.  
  39.  
  40. /** -----GLOBAL VARIABLES----- **/
  41. i64 N, node = 1; 
  42. vector<vi> mask(1, vi(26, -1));
  43. vi outDeg(1, 0); vb End(1, false);
  44.  
  45. /** -----EXTENSIVE FUNCTIONS----- **/
  46.  
  47.  
  48. /** -----COMPULSORY FUNCTIONS----- **/
  49. void VarInput() {
  50. 	cin >> N;
  51. }
  52.  
  53. void ProSolve() {
  54. 	while (N--) {
  55. 		string s; cin >> s;
  56. 		bool newRoad = false, oldExtend = false;
  57. 		i64 position = 0;
  58. 		for (i64 i=0; i<s.size(); i++) {
  59. 			if (mask[position][s[i]-'a'] != -1) {
  60. 				//cout << "following old trail to node " << mask[position][s[i]-'a'] << endl;
  61. 				position = mask[position][s[i]-'a'];
  62. 			}
  63. 			else {
  64. 				if (End[position]) oldExtend = true;
  65. 				outDeg[position]++; newRoad = true;
  66. 				mask.pub(vi(26, -1)); outDeg.pub(0); End.pub(false);
  67. 				mask[position][s[i]-'a'] = node++;
  68. 				position = node - 1;
  69. 				//cout << "new trail to node " << node-1 << endl;
  70. 			}
  71. 		}
  72. 		//cout << "oldExtend = " << (oldExtend ? "true\n" : "false\n");
  73. 		//cout << "newRoad = " << (newRoad ? "true\n" : "false\n");
  74. 		if (oldExtend || !newRoad) {
  75. 			cout << "BAD SET\n" << s << endl; return;
  76. 		}
  77. 		End[position] = true;
  78. 	}
  79. 	cout << "GOOD SET";
  80. }
  81.  
  82. /** -----MAIN FUNCTION----- **/
  83. int main() {
  84. 	//freopen("FILE.INP", "r", stdin);
  85. 	//freopen("FILE.OUT", "w", stdout);
  86. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  87. 	VarInput(); ProSolve(); return 0;
  88. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
4
aabd
jjjjjj
cccc
aabdj
stdout
copy 
BAD SET
aabdj
https://ideone.com/QKMpz8
SPOJ-PTIT | P176PROC (Trie example)
language:
C++ (gcc 8.3)
created:
8 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!