Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.90 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. #include<bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp> // Common file
  5. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  6. using namespace __gnu_pbds;
  7. using namespace std;
  8. #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  9. #define PI 3.1415926535897932384626433832795
  10. #define endl "\n"
  11. #define int long long
  12. #define f first
  13. #define se second
  14. #define pb push_back
  15. #define all(x) x.begin(), x.end()
  16. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  17. long long MOD = 1e9+7;
  18. pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
  19. const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21. struct chash {int operator()(int x) const { return x ^ RANDOM; }};
  22. string toString(long long x){stringstream ss;ss << x;string str = ss.str();return str;}
  23. long long fastpow(long long x,long long k){if(!k)return 1;if(k & 1)return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
  24. long long ans = fastpow(x,k/2);ans %= MOD;ans *= ans;ans %= MOD;return ans;}
  25. long long sumF(long long x){int s = 0;while(x)s += x%10,x /= 10;return s;}
  26. bool isS(char c){return (c >= 'a' && c <= 'z');}
  27. bool isB(char c){return (c >= 'A' && c <= 'Z');}
  28. bool isD(char c){return (c >= '0' && c <= '9');}
  29. bool isSqrt(long long x){ long long f = sqrt((long double)x + 0.5); return f*f == x;}
  30. bool isCubic(long long x) {long long f = cbrt((long double)x + 0.5); return f*f*f == x;}
  31. long long lcm(long long a,long long b){return a * (b / __gcd(a,b));}
  32. vector<long long> divVec(long long x){vector<long long> tmp;for(long long i = 1;1LL*i*i <= x;i++){if(x % i == 0){tmp.push_back(i);if(x / i != i)
  33. tmp.push_back(x / i);}sort(tmp.begin(),tmp.end());}return tmp;}
  34. int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
  35. int primeFactorsCnt(long long n){int ret = 0;if(n % 2 == 0)ret++;while (n % 2 == 0)n = n/2;for (int i = 3; i*i <= n; i = i + 2){if(n % i == 0)ret++;while (n % i == 0)
  36. n = n/i;}if (n > 2)ret++;return ret;}
  37. long long mulmod(long long a,long long b){return ((a % MOD) * (b % MOD)) % MOD;}
  38. long long minusmod(long long a,long long b){return ((((a % MOD) - (b % MOD)) % MOD) + MOD) % MOD;}
  39. long long plusmod(long long a,long long b){return ((a % MOD) + (b % MOD)) % MOD;}
  40. int board[505][505];
  41. int n,m;
  42. const int MX = 505*505 + 10000;
  43. int pp[MX];
  44.  
  45. int par[MX];
  46. int lvl[MX];
  47. int sparse[MX][19];
  48. int sz[MX];
  49. void dfs(int curr ,int par = 0){
  50. lvl[curr] = lvl[par] + 1;
  51. sparse[curr][0] = par;
  52. for(int j : adj)
  53. }
  54. int findpar(int x){
  55. return (x == pp[x]) ? x: pp[x] = findpar(pp[x]);
  56. }
  57. vector<pair<int,int> > adj[MX];
  58. bool join(int a, int b){
  59. int pa = findpar(a);
  60. int pb = findpar(b);
  61. if(pa == pb) return 0;
  62. if(sz[b] > sz[a]){
  63. swap(a,b);
  64. }
  65. pp[b] = a;
  66. sz[a] += sz[b];
  67. return 1;
  68. }
  69. int indx(int i, int j){
  70. return i*n + j;
  71. }
  72. int dx[] = {1,-1,0,0};
  73. int dy[] = {0,0,1,-1};
  74. bool valid(int x, int y){
  75. return x >= 1 && x <= n && y>=1 && y<= m;
  76. }
  77. void getEdges(){
  78. vector<pair<int, pair<int,int> > > edges;
  79. for(int i = 1 ; i <= n ; i++){
  80. for(int j = 1; j <= m ; j++ ){
  81. for(int k = 0 ; k < 4 ; k++){
  82. int nx = i+dx[k];
  83. int ny = j+dy[k];
  84. if(valid(nx,ny)){
  85. int cost = max(board[i][j], board[nx][ny]);
  86. edges.push_back({cost,{indx(i,j), indx(nx, ny)});
  87. }
  88. }
  89. }
  90. }
  91. return edges;
  92. }
  93.  
  94. int32_t main()
  95. {
  96. IO;
  97. cin >> n >> m >> q;
  98. for(int i = 1;i <= n;i++)
  99. {
  100. for(int j = 1;j <= m;j++)
  101. cin >> board[i][j];
  102. }
  103.  
  104. vector<pair<int,pair<int,int> > > edges = getEdges();
  105. sort(all(edges));
  106. for(int i = 1 ; i<= MX ; i++) pp[i] = i;
  107. for(int i = 0 ;i < edges.size() ; i++){
  108. if(join(edges[i].se.f, edges[i].se.se)){
  109. adj[edges[i].se.f].push_back(edges[i].se.se);
  110. adj[edges[i].se.se].push_back(edges[i].se.f);
  111. }
  112. }
  113. dfs(n+1);
  114.  
  115. /*vector<vector<int> > queries(q);
  116. for(int i = 0;i < q;i++)
  117. {
  118. int x1,y1,x2,y2;
  119. cin >> x1 >> y1 >> x2 >> y2;
  120. queries[i] = vector<int>{x1,y1,x2,y2,i};
  121. }*/
  122. return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement