fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(x) (x).begin(),(x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define fi first
  8. #define se second
  9. #define setbits(x) __builtin_popcount(x)
  10. #define zerobits(x) __builtin_ctz(x)
  11. #define setbitsll(x) __builtin_popcountll(x)
  12. #define zerobitsll(x) __builtin_ctzll(x)
  13. #define inf 1e18
  14. #define ps(x,y) fixed<<setprecision(y)<<x
  15.  
  16. typedef vector<int> vi;
  17. typedef long long ll;
  18. typedef vector<ll> vl;
  19. typedef pair<int,int> pii;
  20. typedef unsigned long long ull;
  21. typedef map<int,int> mii;
  22.  
  23. const int MOD = 1e9+7;
  24. const int maxN = 2e5+1;
  25. long double EPS = 1e-9;
  26. //vi vect[maxN];
  27. int parent[maxN];
  28. int	n,m,u,v;
  29.  
  30. int find (int a) {
  31. 	if (parent[a] == a) {
  32. 		return a;
  33. 	}
  34. 	int x = find(parent[a]);
  35. 	parent[a] = x;
  36. 	return x;
  37. }
  38.  
  39. void solve () {
  40. 	cin >> n >> m;
  41. 	for (int i = 1;i <= n;++i) {
  42. 		//vect[i].clear();
  43. 		parent[i] = i;
  44. 	}
  45.  
  46. 	vector<long double>val;
  47. 	vi a(n+1),b(n+1);
  48. 	for (int i = 1;i <= n;++i) {
  49. 		cin >> a[i];
  50. 	}
  51. 	for (int i = 1;i <= n;++i) {
  52. 		cin >> b[i];
  53. 	}
  54. 	for (int i = 1;i <= n;++i) {
  55. 		val.pb((long double)a[i]/b[i]);
  56. 	}
  57. 	long double maxi = 0;
  58. 	for (int i = 0;i < n;++i) {
  59. 		if (maxi < val[i]) {
  60. 			maxi = val[i];
  61. 		}
  62. 	}
  63. 	for (int i = 1;i <= m;++i) {
  64. 		cin >> u >> v;
  65. 		int x = find(u);
  66. 		int y = find(v);
  67. 		if (x != y) {
  68. 			if (x < y) {
  69. 				parent[y] = x;
  70. 			} else {
  71. 				parent[x] = y;
  72. 			}
  73. 		}
  74. 	}
  75. 	vi temp;
  76. 	for (int i = 0;i < n;++i) {
  77. 		if (abs(val[i]-maxi) < EPS) {
  78. 			temp.pb(i+1);
  79. 		}
  80. 	}
  81. 	mii ma;
  82. 	for (int x : temp) {
  83. 		ma[parent[x]]++;
  84. 		//cout << x << '\n';
  85. 	}
  86. 	int ans = 0;
  87. 	int par = -1;
  88. 	for (auto x : ma) {
  89. 		if (x.se >= ans) {
  90. 			ans = x.se;
  91. 			par = x.fi;
  92. 		}
  93. 	}
  94. 	cout << ans << '\n';
  95. 	for (int x : temp) {
  96. 		if (parent[x] == par) {
  97. 			cout << x << " ";
  98. 		}
  99. 	}
  100. 	cout << '\n';
  101. }
  102.  
  103. int main()
  104. {
  105. 	ios_base::sync_with_stdio(false);
  106. 	cin.tie(NULL);
  107. 	int t;
  108. 	cin >> t;
  109. 	while (t--) {
  110. 		solve();
  111. 	}
  112. 	return 0;
  113. }
  114.  
  115.  
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
1
3 3
10 1 2
5 1 1 
1 2
2 3
1 3
stdout
copy 
2
1 3
https://ideone.com/7VoHLS
language:
C++14 (gcc 8.3)
created:
5 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!