fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define MAX 160100
  6.  
  7. int height[MAX], excess[MAX];
  8. int s, t, N;
  9.  
  10. class Edge{
  11. public:
  12. 	int from, to, cap, flow, res_flow, index;
  13.  
  14. 	Edge(int from, int to, int cap, int flow, int res_flow, int index):
  15. 		from(from),to(to),cap(cap),flow(flow),res_flow(res_flow),index(index){
  16. 	}
  17. };
  18.  
  19. vector<vector<Edge> > G;
  20.  
  21. void addEdge(int from, int to, int cap){
  22. 	Edge ed(from, to, cap, 0, cap, G[to].size());
  23. 	Edge ed_rev(to, from, 0, 0, 0, G[from].size());
  24. 	G[from].pb(ed);
  25. 	G[to].pb(ed_rev);
  26. }
  27.  
  28. void initializePreflow(){
  29. 	memset(height, 0, sizeof(height));
  30. 	height[s] = N;
  31. 	memset(excess, 0, sizeof(excess));
  32. 	int v;
  33. 	for(int i=0; i<G[s].size(); i++){
  34. 		v = G[s][i].to;
  35. 		G[s][i].flow = G[s][i].cap;
  36. 		G[v][G[s][i].index].flow = -G[s][i].cap;
  37.  
  38. 		excess[v] = G[s][i].cap;
  39. 		excess[s] -= G[s][i].cap;
  40.  
  41. 		G[s][i].res_flow = G[s][i].cap - G[s][i].flow;
  42. 		G[v][G[s][i].index].res_flow = G[v][G[s][i].index].cap - G[v][G[s][i].index].flow;
  43. 	}
  44. }
  45.  
  46. void push(int u, int i){
  47. 	int amt = min(excess[u], G[u][i].res_flow);
  48. 	G[u][i].flow = G[u][i].flow + amt;
  49. 	int v = G[u][i].to;
  50. 	G[v][G[u][i].index].flow = -G[u][i].flow;
  51. 	excess[u] = excess[u]-amt;
  52. 	excess[v] = excess[v]+amt;
  53. 	G[u][i].res_flow = G[u][i].cap - G[u][i].flow;
  54. 	G[v][G[u][i].index].res_flow = G[v][G[u][i].index].cap - G[v][G[u][i].index].flow;
  55. }
  56.  
  57. void displayG(){
  58. 	for(int i=0;i<N;i++){
  59. 		cout << i << ": ";
  60. 		for(int j=0;j<G[i].size();j++){
  61. 			cout << "-> (" << G[i][j].to << "," << G[i][j].cap << ") ";
  62. 		}
  63. 		cout << endl;
  64. 	}
  65. }
  66.  
  67. int maxFlow(int s, int t){
  68. 	initializePreflow();
  69. 	queue<int> q;
  70. 	int active[N];
  71. 	memset(active,0,sizeof(active));
  72. 	for(int i=0;i<G[s].size();i++){
  73. 		if(G[s][i].to != t){
  74. 			q.push(G[s][i].to);
  75. 			active[G[s][i].to] = 1;
  76. 		}
  77. 	}
  78. 	int u,minimum;
  79. 	while(q.size()!=0){
  80. 		u = q.front();
  81. 		//cout << "processing: " << u << "...\n";
  82. 		minimum = -1;
  83. 		for(int i=0; i<G[u].size() && excess[u]>0; i++){
  84. 			int v = G[u][i].to;
  85. 			if(G[u][i].res_flow>0){
  86. 				if(height[u]>height[v]){
  87. 					push(u,i);
  88. 					if(!active[v] && v!=s && v!=t){
  89. 						active[v] = 1;
  90. 						q.push(v);
  91. 					}
  92. 				} else if(minimum==-1){
  93. 					minimum = height[v];
  94. 				} else{
  95. 					minimum = min(minimum, height[v]);
  96. 				}
  97. 			}
  98. 		}
  99. 		if(excess[u]!=0)
  100. 			height[u] = 1+minimum;
  101. 		else{
  102. 			active[u] = 0;
  103. 			q.pop();
  104. 		}
  105. 	}
  106. 	return excess[t];
  107. 	/*
  108. 	int tot_flow = 0;
  109. 	for(int i=0; i<G[s].size();i++){
  110. 		tot_flow += G[s][i].flow;
  111. 	}
  112. 	return tot_flow;
  113. 	*/
  114. }
  115.  
  116. vector<int> vA, primes;
  117. vector<int> middle;
  118. map<int,int> gL, gR;
  119.  
  120. const int limit = 31650; //sqrt(10^9)
  121. const int max_factor = 10;
  122. const int inf = 1000000000;
  123. bool is_prime[limit+1];
  124.  
  125.  
  126. int gcd(int a, int b){
  127. 	if(b==0)
  128. 		return a;
  129. 	return gcd(b,a%b);
  130. }
  131.  
  132. vector<int> factorize(int x){
  133. 	vector<int> ret;
  134. 	for(int i=0; i<primes.size() && primes[i]*primes[i]<=x; i++){
  135. 		int d = primes[i];
  136. 		if(x%d==0){
  137. 			ret.pb(d);
  138. 			middle.pb(d);
  139. 			while(x%d==0){
  140. 				x /= d;
  141. 			}
  142. 		}
  143. 	}
  144. 	if(x>1){
  145. 		ret.pb(x);
  146. 		middle.pb(x);
  147. 	}
  148. 	return ret;
  149. }
  150.  
  151. void fillPrimes(){
  152. 	memset(is_prime, true, sizeof(is_prime));
  153. 	for(int i=2;i<=limit;i++){
  154. 		if(is_prime[i]){
  155. 			primes.pb(i);
  156. 			for(int j=i*i; j<=limit;j+=i){
  157. 				is_prime[j] = false;
  158. 			}
  159. 		}
  160. 	}
  161. }
  162.  
  163. int main(){
  164.  
  165. 	fillPrimes();
  166. 	int tcs;
  167. 	cin >> tcs;
  168. 	while(tcs--){
  169. 		int n;
  170. 		cin >> n;
  171.  
  172.     	gL.clear(); gR.clear();
  173.     	vA.clear();
  174.  
  175.     	int x;
  176.     	for(int i = 0; i < n; i++){
  177.       		cin >> x;
  178.       		vA.push_back(x);
  179.     	}
  180.  
  181.     	int g;
  182.     	for(int j = 0; j < n; j++){
  183.     		cin >> x;
  184.     		for(int i = 0; i < n; i++){
  185.     			if(vA[i] < x){ // Left
  186.           			g = gcd(vA[i],x);
  187.           			if(g > 1){
  188.             			if(!gL.count(g)){
  189.               				gL[g] = 0;
  190.             			}
  191.             			gL[g]++;
  192.           			}
  193.         		}
  194.         		else if(vA[i] > x){ // Right
  195.           			g = gcd(vA[i],x);
  196.           			if(g > 1){
  197.             			if(!gR.count(g)){
  198.               				gR[g] = 0;
  199.             			}
  200.             			gR[g]++;
  201.           			}
  202.         		}
  203.       		}
  204.     	}
  205.  
  206.     	map<int,int>::const_iterator it, it2;
  207.     	int id, id2;
  208.  
  209.     	vector<vector<int> > left_factors, right_factors;
  210.     	middle.clear();
  211.  
  212.     	for(it = gL.begin(), id = 1; it != gL.end(); ++it, id++){
  213.       		//addEdge(source, id, it->second);
  214.       		left_factors.pb(factorize(it->first)); //this also adds them to middle
  215.  
  216.     	}
  217.     	for(it = gR.begin(), id = gL.size()+1;it != gR.end(); it++, id++){
  218.       		//addEdge(id, target, it->second);
  219.       		right_factors.pb(factorize(it->first)); //this also adds them to middle
  220.     	}
  221.  
  222.     	sort(middle.begin(), middle.end()); // sorts the middle nodes
  223.     	middle.erase( unique(middle.begin(), middle.end()), middle.end() ); // removes duplicates and erases the space
  224.  
  225.     	G.clear();
  226.     	N = gL.size()+middle.size()+gR.size()+2;
  227.     	G.resize(N);
  228. 	int source = 0, target = N-1;
  229. 	s = source;
  230. 	t = target;	
  231. 	int sz,k, ind;
  232.     	for(it = gL.begin(), id = 1, ind = 0; it != gL.end(); ++it, id++, ind++){
  233.       		addEdge(source, id, it->second);
  234.       		sz = left_factors[ind].size();
  235.       		for(int j=0;j<sz;j++){
  236.       			k = lower_bound(middle.begin(),middle.end(),it->first)-middle.begin();
  237.       			addEdge(id,gL.size()+k+1,inf);
  238.       		}
  239.     	}
  240.  
  241.     	for(it = gR.begin(), id = gL.size()+middle.size()+1, ind = 0;it != gR.end(); it++, id++, ind++){
  242.       		addEdge(id, target, it->second);
  243.       		sz = right_factors[ind].size();
  244.       		for(int j=0;j<sz;j++){
  245.       			k = lower_bound(middle.begin(),middle.end(),it->first)-middle.begin();
  246.       			addEdge(gL.size()+k+1, id, inf);
  247.       		}
  248.     	}
  249.  
  250.  
  251.     	//displayG();
  252.  
  253.     	cout << maxFlow(source, target) << endl;
  254. 	}
  255. 	return 0;
  256. }
  257.  
  258. /*	
  259. 	N = 7;
  260. 	s = 0;
  261. 	t = 6;
  262. 	G.resize(N);
  263. 	addEdge(0,1,6);
  264. 	addEdge(0,3,8);
  265. 	addEdge(1,3,1);
  266. 	addEdge(1,2,6);
  267. 	addEdge(3,4,3);
  268. 	addEdge(4,1,6);
  269. 	addEdge(4,5,6);
  270. 	addEdge(2,4,2);
  271. 	addEdge(2,5,2);
  272. 	addEdge(2,6,3);
  273. 	addEdge(5,6,6);
  274.  
  275. 	//displayG();
  276.  
  277. 	N = 7;
  278. 	s = 0;
  279. 	t = 6;
  280. 	G.resize(7);
  281. 	addEdge(0,1,3);
  282. 	addEdge(1,3,3);
  283. 	addEdge(3,6,3);
  284. 	addEdge(0,2,1);
  285. 	addEdge(4,6,1);
  286. 	addEdge(5,6,1);
  287. 	cout << maxFlow(s,t) << endl;
  288. */
Success #stdin #stdout 0s 4776KB
comments (?)
stdin
copy 
2
4
2 5 6 14
3 4 7 10
2
2 3
5 7
stdout
copy 
3
0
https://ideone.com/jHrJZX
language:
C++ (gcc 8.3)
created:
9 years 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!