fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.FileNotFoundException;
  3. import java.io.FileReader;
  4. import java.io.IOException;
  5. import java.io.InputStream;
  6. import java.io.InputStreamReader;
  7. import java.io.PrintWriter;
  8. import java.util.ArrayList;
  9. import java.util.Collections;
  10. import java.util.StringTokenizer;
  11. import java.util.TreeSet;
  12.  
  13. public class Main {
  14.  
  15.  
  16. 	static class DSU 
  17. 	{
  18. 		int rank[];
  19. 		int parent[];
  20. 		int N;
  21. 		int sets;
  22. 		int setsize[];
  23.  
  24. 		public DSU(int N)
  25. 		{
  26. 			this.N = N;
  27. 			sets = N;
  28. 			parent = new int[N];
  29. 			rank = new int[N];
  30. 			setsize = new int[N];
  31. 			for(int i=0;i<N;i++){ parent[i] = i; setsize[i] = 1; }
  32.  
  33. 		}
  34.  
  35. 		public void union(int x,int y)
  36. 		{
  37. 			if(isSameSet(x,y)) return;
  38. 			sets--;
  39. 			int xp = getParent(x);
  40. 			int yp = getParent(y);
  41. 			if(rank[xp]>rank[yp]){ parent[yp] = xp; setsize[xp]+=setsize[yp];}
  42. 			else{
  43. 				if(rank[xp]==rank[yp]){
  44. 					rank[yp]++;
  45. 					parent[xp] = yp;
  46. 					setsize[yp]+=setsize[xp];
  47. 				}
  48. 				else
  49. 				{ parent[xp] =yp; setsize[yp] += setsize[xp]; }
  50. 			}
  51.  
  52. 		}
  53.  
  54. 		public int getParent(int x){
  55. 			if(x==parent[x]) return x;
  56. 			return parent[x] = getParent(parent[x]);
  57. 		}
  58.  
  59. 		public boolean isSameSet(int x,int y){
  60. 			return getParent(x)==getParent(y);
  61. 		}
  62.  
  63. 		public int numDisjointSets(){
  64. 			return sets;
  65. 		}
  66. 		public int getSetSize(int x){
  67. 			return setsize[getParent(x)];
  68. 		}
  69.  
  70.  
  71.  
  72. 	}
  73.  
  74. 	static ArrayList<Integer> div[];
  75. 	public static void main(String[]args)throws Throwable {
  76. 		Scanner sc = new Scanner("dream.in");
  77. 		PrintWriter out = new PrintWriter(System.out);
  78. 		int t = sc.nextInt();
  79. 		int max = (int)1e5;
  80. 		div = new ArrayList[max + 1];
  81.  
  82. 		int tc = 1;
  83. 		while(t-- > 0) {
  84. 			for(int i = 0 ; i < max + 1 ; ++i) {
  85. 				div[i] = new ArrayList();
  86. 			}
  87. 			int n = sc.nextInt();
  88. 			for(int i = 0 ; i < n ; ++i) {
  89. 				div[sc.nextInt()].add(i);
  90. 			}
  91. 			DSU dsu = new DSU(n);
  92. 			long sum = 0;
  93. 			for(int i = max ; i >= 1 ; --i) {
  94. 				int lead = -1;
  95. 				for(int j = i ; j <= max ; j += i ) {
  96. 					ArrayList<Integer> arr = div[j];
  97.  
  98. 					if(arr.size() > 0 && lead == -1) {
  99. 						lead = arr.get(0);
  100. 					}
  101. 					if(lead != -1) {
  102. 						for(Integer x : arr) {
  103. 							if(dsu.isSameSet(lead, x))
  104. 								continue;
  105. 							dsu.union(lead, x);
  106. 							sum += i;
  107.  
  108. 						}
  109. 					}
  110. 				}
  111. 			}
  112. 			out.printf("Case %d: %d\n",tc++,sum);
  113.  
  114. 		}
  115. 		out.flush();
  116. 		out.close();
  117.  
  118. 	}
  119. 	static class Scanner
  120. 	{
  121. 		BufferedReader br;
  122. 		StringTokenizer st;
  123.  
  124.  
  125. 		Scanner(InputStream s)  { br = new BufferedReader(new InputStreamReader(s)); }
  126. 		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}
  127.  
  128.  
  129. 		String next() throws IOException
  130. 		{
  131.  
  132. 			while(st == null || !st.hasMoreTokens())
  133. 				st = new StringTokenizer(br.readLine());
  134. 			return st.nextToken();
  135.  
  136. 		}
  137. 		double nextDouble() throws NumberFormatException, IOException { return Double.parseDouble(next()); }
  138.  
  139. 		int nextInt() throws NumberFormatException, IOException { return Integer.parseInt(next()); }
  140. 		long nextLong() throws NumberFormatException, IOException { return Long.parseLong(next()); }
  141.  
  142.  
  143.  
  144.  
  145. 	}
  146. }
Runtime error #stdin #stdout #stderr 0.04s 4575232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.io.FileNotFoundException: dream.in (No such file or directory)
	at java.io.FileInputStream.open0(Native Method)
	at java.io.FileInputStream.open(FileInputStream.java:195)
	at java.io.FileInputStream.<init>(FileInputStream.java:138)
	at java.io.FileInputStream.<init>(FileInputStream.java:93)
	at java.io.FileReader.<init>(FileReader.java:58)
	at Main$Scanner.<init>(Main.java:126)
	at Main.main(Main.java:76)
https://ideone.com/Vbkhnw
language:
Java (HotSpot 12)
created:
6 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!