fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define mp make_pair
  4. #define INF 1000000001
  5. #define LL long long int
  6.  
  7. using namespace std;
  8.  
  9. int n, k;
  10. vector < vector<int> > g;
  11. vector<int> mt;
  12. vector<bool> used;
  13.  
  14. bool try_kuhn (int v) {
  15. 	if (used[v])  return false;
  16. 	used[v] = true;
  17. 	for (size_t i=0; i<g[v].size(); ++i) {
  18. 		int to = g[v][i];
  19. 		if (mt[to] == -1 || try_kuhn (mt[to])) {
  20. 			mt[to] = v;
  21. 			return true;
  22. 		}
  23. 	}
  24. 	return false;
  25. }
  26.  
  27.  
  28. int main () {
  29.  
  30.     int n;
  31.     cin >> n;
  32.     k = n;
  33.     int a[n+1],b[n+1];
  34.     g.resize(n+1); mt.resize(n+1);
  35.  
  36.     mt.assign (n+1, -1);
  37.  
  38.     for(int i=1;i<=n;i++)
  39.         scanf("%d",&a[i]);
  40.  
  41.     for(int i=1;i<=n;i++)
  42.         scanf("%d",&b[i]);
  43.  
  44.     for(int i=1;i<=n;i++)
  45.         for(int j=1;j<=n;j++)
  46.             if(__gcd(a[i],b[j])!=1)
  47.                  g[i].pb(j);
  48.  
  49. // BIPARTITE MATCHING USING KUHNS ALGORITHM
  50.  
  51.     vector<char> used1 (n);
  52. 	for (int i=1; i<=n; ++i)
  53. 		for (size_t j=0; j<g[i].size(); ++j)
  54. 			if (mt[g[i][j]] == -1) {
  55. 				mt[g[i][j]] = i;
  56. 				used1[i] = true;
  57. 				break;
  58. 			}
  59.  
  60.     for (int v=1; v<=n; ++v) {
  61. 		if (used1[v])  continue;
  62. 		used.assign (n, false);
  63. 		try_kuhn (v);
  64. 	}
  65.  
  66.     int ans = 0;
  67.  
  68. 	for (int i=1; i<=n; ++i)
  69. 		if (mt[i] != -1){
  70. 		//	printf ("%d %d\n", mt[i], i);
  71.             ans++;
  72. 		}
  73.  
  74.  
  75.     cout << ans;
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
4
2 5 6 7
4 9 10 12
stdout
copy 
3
https://ideone.com/2uj2OD
language:
C++14 (gcc 8.3)
created:
9 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!