fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11. 	public static int[] parent = new int[10000];
  12. 	public static int[] sz = new int[10000];
  13.  
  14. 	public static void make(int i){
  15. 		parent[i] = i;
  16. 		sz[i] = 1;
  17. 	}
  18.  
  19. 	public static int find(int i){
  20. 		if(parent[i] == i){
  21. 			return i;
  22. 		}else{
  23. 			return (parent[i] = find(parent[i]));
  24. 		}
  25. 	}
  26.  
  27. 	public static void unite(int a, int b){
  28. 		int root1 = find(a);
  29. 		int root2 = find(b);
  30.  
  31. 		if(root1 == root2){
  32.  
  33. 		}else{
  34. 			if(sz[root1] < sz[root2]){
  35. 				int temp = root1;
  36. 				root1 = root2;
  37. 				root2 = temp;
  38. 			}
  39. 			parent[root2] = root1;
  40. 			sz[root1] = sz[root2] + sz[root1];
  41. 		}
  42. 	}
  43.  
  44. 	public static void main (String[] args) throws java.lang.Exception
  45. 	{
  46. 		// your code goes here
  47.  
  48. 		Scanner sc = new Scanner(System.in);
  49. 		int N = sc.nextInt();
  50. 		for(int i = 1; i <= N; i++){
  51. 			make(i);
  52. 		}
  53. 		int E = sc.nextInt();
  54. 		int Q = sc.nextInt();
  55. 		int[] ans = new int[Q];
  56.  
  57. 		int[][] edges = new int[E][3];
  58. 		for(int i = 0; i < E; i++){
  59. 			int u = sc.nextInt();
  60. 			edges[i][1] =  u;
  61. 			int v = sc.nextInt();
  62. 			edges[i][2] = v;
  63. 			int w = sc.nextInt();
  64. 			edges[i][0] = w;
  65. 			sc.nextLine();
  66. 		}
  67.  
  68. 		Arrays.sort(edges, (a,b) -> Integer.compare(a[0], b[0]));
  69.  
  70. 		int[][] queries = new int[Q][4];
  71. 		for(int i = 0; i < Q; i++){
  72. 			queries[i][3] = i;
  73. 			int u = sc.nextInt();
  74. 			queries[i][1] =  u;
  75. 			int v = sc.nextInt();
  76. 			queries[i][2] = v;
  77. 			int w = sc.nextInt();
  78. 			queries[i][0] = w;
  79. 		}
  80. 		Arrays.sort(queries, (a,b) -> Integer.compare(a[0], b[0]));
  81.  
  82. 		int j = 0;
  83. 		for(int i = 0; i < E; i++){
  84. 			int w = edges[i][0];
  85. 			int u = edges[i][1];
  86. 			int v = edges[i][2];
  87. 			unite(u, v);
  88. 			if(i == E-1 || edges[i][0] != edges[i+1][0]){
  89. 				int left = edges[i][0];
  90. 				int right;
  91. 				if(i==E-1){
  92. 					right = 10000;
  93. 				}else{
  94. 					right = edges[i+1][0] - 1;
  95. 				}
  96. 				while(j <= Q - 1 && queries[j][0] <= right){
  97. 					if(queries[j][0] < left){
  98.  
  99. 					}else{
  100. 						int node1 = queries[j][1];
  101. 						int node2 = queries[j][2];
  102. 						int idx = queries[j][3];
  103.  
  104. 						if(find(node1) == find(node2)){
  105. 							ans[idx] = 1;
  106. 						}
  107. 					}
  108. 					j++;
  109. 				}
  110. 			}else{
  111.  
  112. 			}
  113. 		}
  114. 		for(int x : ans){
  115. 			System.out.println(x);
  116. 		}
  117. 	}
  118. }
Success #stdin #stdout 0.11s 56600KB
comments (?)
stdin
copy 
5 4 2 
1 2 10
2 3 5
3 4 9
4 5 13
1 5 13
2 5 12
stdout
copy 
1
0
https://ideone.com/Tgf0jM
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

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!