fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pb push_back
  6. #define REP(i,n) for (int i = 0; i < n; i++)
  7. #define FOR(i,a,b) for (int i = a; i < b; i++)
  8. #define remax(a,b) a = max(a,b)
  9. #define all(v) v.begin(),v.end()
  10. typedef map<int,int> mii;
  11. typedef pair<int,int> pii;	
  12. #define F first
  13. #define S second
  14. #define WL(t) while(t --)
  15.  
  16. #define sfl(x) scanf("%lld",&x);
  17. #define sfi(x) scanf("%d",&x);
  18. #define sfi2(x,y) scanf("%d%d",&x,&y);
  19. #define pfi(x) printf("%d\n",x);
  20.  
  21. #define TRACE
  22.  
  23. #ifdef TRACE
  24. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  25. template <typename Arg1>
  26. void __f(const char* name, Arg1&& arg1){
  27. 	cerr << name << " : " << arg1 << std::endl;
  28. }
  29. template <typename Arg1, typename... Args>
  30. void __f(const char* names, Arg1&& arg1, Args&&... args){
  31. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  32. }
  33. #else
  34. #define trace(...)
  35. #endif
  36.  
  37. void solvethetestcase();
  38.  
  39. signed main(){
  40. 	int t;
  41. 	sfi(t);
  42. 	WL(t){
  43. 		solvethetestcase();
  44. 	}
  45. }   
  46.  
  47. int n,m,dp[100005];
  48. ll a[100005];
  49. vector<pair<ll,pii> > edges;
  50. mii cur;
  51.  
  52. void solvethetestcase(){
  53. 	sfi2(n,m)
  54. 	edges.clear();
  55. 	FOR(i,1,n+1){
  56. 		sfl(a[i])
  57. 		dp[i] = 1;
  58. 	}
  59. 	REP(i,m){
  60. 		int u,v; sfi2(u,v)
  61. 		if(a[u] > a[v]){
  62. 			edges.pb({a[u]-a[v],{v,u}});
  63. 		}
  64. 		else if(a[v] > a[u]){
  65. 			edges.pb({a[v]-a[u],{u,v}});
  66. 		}
  67. 	}
  68. 	sort(all(edges));
  69. 	int ans = 1;
  70. 	int i = 0;
  71. 	while(i < edges.size()){
  72. 		cur.clear();
  73. 		if(dp[edges[i].S.S] < dp[edges[i].S.F]+1){
  74. 			cur[edges[i].S.S] = dp[edges[i].S.F]+1;
  75. 		}
  76. 		for(int j = i+1; j <= edges.size(); j ++){
  77. 			if(j == edges.size() or edges[j].F != edges[j-1].F){
  78. 				i = j;
  79. 				break;
  80. 			}
  81. 			if(dp[edges[j].S.S] < dp[edges[j].S.F]+1){
  82. 				if(cur.find(edges[j].S.S) == cur.end()){
  83. 					cur[edges[j].S.S] = dp[edges[j].S.F]+1;
  84. 				}
  85. 				else{
  86. 					remax(cur[edges[j].S.S],dp[edges[j].S.F]+1);
  87. 				}
  88. 			}
  89. 		}
  90. 		for(auto x:cur) dp[x.F] = x.S; 
  91. 	}
  92. 	FOR(i,1,n+1){
  93. 		if(dp[i] > ans) ans = dp[i];
  94. 	}
  95. 	pfi(ans)
  96. }
Success #stdin #stdout 0s 16416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/scCzZm
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!