0
Your rating: None

CodeChef submission 624498 (C++ 4.3.2)

CodeChef submission 624498 (C++ 4.3.2) plaintext list. Status: WA, problem COMPLEXT, contest AUG11. By rajneesh2k10 (rajneesh2k10), 2011-08-12 14:44:29.
  1. #include <cstdio>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5. #include <map>
  6. #define SIZE 402
  7. #define MAX 99999
  8. using namespace std;
  9. set<int> visited;
  10. set<pair<int,int> > result;
  11. vector<vector<pair<int,int> > > input;
  12. vector<pair<int,pair<int,int> > > next;
  13. int n,n2;
  14. int adjmat[SIZE][SIZE];
  15.  
  16. void initialize() {
  17. 	for (int i = 0; i < SIZE; ++i)
  18. 		for (int j = 0; j < SIZE; ++j)
  19. 			adjmat[i][j] = MAX;
  20. }
  21.  
  22. void createAdjacencyList() {
  23. 	vector<pair<int,int> > temp;
  24. 	pair<int,int> pr;
  25. 	for (int i = 1; i <= n2; ++i) {
  26. 		temp.clear();
  27. 		for (int j = 1; j <= n2; ++j) {
  28. 			if (adjmat[i][j] != MAX) {
  29. 				pr = pair<int,int>(adjmat[i][j],j-1);
  30. 				temp.push_back(pr);
  31. 			}
  32. 		}
  33. 		input.push_back(temp);
  34. 	}
  35. }
  36.  
  37. void prune (int nd) {
  38. 	pair<int,int> edge;
  39. 	pair<int,pair<int,int> > in;
  40. 	for (unsigned int i = 0; i < input[nd].size(); ++i) {
  41. 		if (visited.find(input[nd][i].second) == visited.end()) {
  42. 			edge.first = nd;
  43. 			edge.second = input[nd][i].second;
  44. 			in.first = input[nd][i].first;
  45. 			in.second = edge;
  46. 			next.push_back(in);
  47. 			push_heap(next.begin(),next.end());
  48. 		}
  49. 	}
  50. }
  51.  
  52. void display() {
  53. 	set<pair<int,int> >::iterator it = result.begin();
  54. 	while(it != result.end()) {
  55. 		printf("%d %d %d %d\n",(*it).first/n+1,(*it).first%n+1,(*it).second/n+1,(*it).second%n+1);
  56. 		it++;
  57. 	}
  58. }
  59.  
  60. void solve() {
  61. 	pair<int,pair<int,int> > node;
  62. 	createAdjacencyList();
  63. 	for (unsigned int i = 1; i < input.size(); ++i)
  64. 		sort(input[i].begin(),input[i].end());
  65. 	prune(3);
  66. 	visited.insert(3);
  67. 	int count = 0;
  68. 	while (count < n2-2) {
  69. 		pop_heap(next.begin(),next.end());
  70. 		node = next.back();
  71. 		next.pop_back();
  72. 		if (visited.find(node.second.second) != visited.end())
  73. 			continue;
  74. 		visited.insert(node.second.second);
  75. 		result.insert(pair<int,int>(node.second.first,node.second.second));
  76. 		prune(node.second.second);
  77. 		count++;
  78. 	}
  79. 	display();	
  80. }
  81.  
  82. int main() {
  83. 	initialize();
  84. 	int a,b,k=1;
  85. 	scanf("%d",&n);
  86. 	n2 = n*n;
  87. 	for (int i = 0; i < n; ++i) {
  88. 		for (int j = 0; j < n-1; ++j) {
  89. 			scanf("%d %d",&a,&b);
  90. 			adjmat[k][k+1] = b;
  91. 			adjmat[k+1][k] = b;
  92. 			k++;
  93. 		}
  94. 		k++;
  95. 	}
  96. 	k=1;
  97. 	for (int i = 0; i < n; ++i) {
  98. 		for (int j = 0; j < n-1; ++j) {
  99. 			scanf("%d %d",&a,&b);
  100. 			adjmat[k][k+n] = b;
  101. 			adjmat[k+n][k] = b;
  102. 			k+=n;
  103. 		}
  104. 		k=i+2;
  105. 	}
  106. 	solve();
  107. 	return 0;
  108. }
  109.

Comments