fork(3) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. void solve() {
  8. 	int N, M;
  9. 	cin >> N >> M;
  10. 	vector<int> A(N);
  11. 	for(int i = 0; i < N; i++) {
  12. 		cin >> A[i];
  13. 	}
  14. 	vector<vector<int>> g(N);
  15. 	vector<vector<int>> dp(N);
  16. 	for(int i = 0; i < M; i++) {
  17. 		int u, v;
  18. 		cin >> u >> v;
  19. 		u--, v--;
  20. 		if(A[u] > A[v]) {
  21. 			swap(u, v);
  22. 		} else if(A[u] == A[v]) {
  23. 			continue;
  24. 		}
  25. 		g[u].push_back(v);
  26. 	}
  27. 	vector<int> p(N);
  28. 	iota(begin(p), end(p), 0);
  29. 	sort(begin(p), end(p), [&](int a, int b){return A[a] > A[b];});
  30. 	int ans = 1;
  31. 	for(auto u: p) {
  32. 		sort(begin(g[u]), end(g[u]), [&](int a, int b){return A[a] > A[b];});
  33. 		int cur = 2;
  34. 		for(auto v: g[u]) {
  35. 			auto it = lower_bound(begin(g[v]), end(g[v]), 2 * A[v] - A[u], 
  36. 				[&](int w, int c){
  37. 					return A[w] > c;
  38. 				});
  39. 			if(it != begin(g[v])) {
  40. 				cur = max(cur, 1 + dp[v][it - begin(g[v]) - 1]);
  41. 			}
  42. 			ans = max(ans, cur);
  43. 			dp[u].push_back(cur);
  44. 		}
  45. 	}
  46. 	cout << ans << endl;
  47. }
  48.  
  49. signed main() {
  50. 	//freopen("input.txt", "r", stdin);
  51. 	ios::sync_with_stdio(0);
  52. 	cin.tie(0);
  53. 	int t;
  54. 	cin >> t;
  55. 	while(t--) {
  56. 		solve();
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4AbmwN
language:
C++14 (gcc 8.3)
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!