fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node {
  6. 	node* next[10];
  7. 	int cnt = 0;
  8. 	node() {
  9. 		for (int i = 0; i < 10; i++)
  10. 			next[i] = nullptr;
  11. 		cnt = 0;
  12. 	}
  13. };
  14.  
  15. node* root = new node();
  16.  
  17. void add(string& s) {
  18. 	node* now = root;
  19. 	for (int i = 0; i < (int)s.size(); i++) {
  20. 		if (now -> next[s[i] - '0'] == nullptr)
  21. 			now -> next[s[i] - '0'] = new node();
  22. 		now = now -> next[s[i] - '0'];
  23. 	}	 
  24. 	now -> cnt += 1;
  25. }
  26.  
  27. bool flag = true;
  28.  
  29. void dfs(node* now = root, int was = 0) {
  30. 	if (now -> cnt && was) flag = false;
  31. 	for (int i = 0; i < 10; i++) {
  32. 		if (now -> next[i] != nullptr) {
  33. 			dfs(now -> next[i], max(now -> cnt, was));
  34. 		}  	
  35. 	}
  36. }
  37.  
  38. int main() {
  39. 	int t;
  40. 	cin >> t;
  41. 	while(t--) {
  42. 		root = new node();
  43. 		int n;
  44. 		cin >> n;
  45. 		while(n--) {
  46. 			string s;
  47. 			cin >> s;
  48. 			add(s);
  49. 		}
  50. 		flag = true;
  51. 		dfs();
  52. 		if (flag)
  53. 			cout << "YES\n";
  54. 		else
  55. 			cout << "NO\n";
  56. 	}
  57. 	return 0;
  58. }
  59.  
Time limit exceeded #stdin #stdout 5s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YXgfIM
language:
C++14 (gcc 8.3)
created:
7 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!