Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp> // Common file
- #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
- using namespace __gnu_pbds;
- using namespace std;
- #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
- #define PI 3.1415926535897932384626433832795
- #define endl "\n"
- #define int long long
- #define f first
- #define se second
- #define pb push_back
- #define all(x) x.begin(), x.end()
- typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- long long MOD = 1e9+7;
- pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
- const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- struct chash {int operator()(int x) const { return x ^ RANDOM; }};
- string toString(long long x){stringstream ss;ss << x;string str = ss.str();return str;}
- 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;
- long long ans = fastpow(x,k/2);ans %= MOD;ans *= ans;ans %= MOD;return ans;}
- long long sumF(long long x){int s = 0;while(x)s += x%10,x /= 10;return s;}
- bool isS(char c){return (c >= 'a' && c <= 'z');}
- bool isB(char c){return (c >= 'A' && c <= 'Z');}
- bool isD(char c){return (c >= '0' && c <= '9');}
- bool isSqrt(long long x){ long long f = sqrt((long double)x + 0.5); return f*f == x;}
- bool isCubic(long long x) {long long f = cbrt((long double)x + 0.5); return f*f*f == x;}
- long long lcm(long long a,long long b){return a * (b / __gcd(a,b));}
- 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)
- tmp.push_back(x / i);}sort(tmp.begin(),tmp.end());}return tmp;}
- int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
- 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)
- n = n/i;}if (n > 2)ret++;return ret;}
- long long mulmod(long long a,long long b){return ((a % MOD) * (b % MOD)) % MOD;}
- long long minusmod(long long a,long long b){return ((((a % MOD) - (b % MOD)) % MOD) + MOD) % MOD;}
- long long plusmod(long long a,long long b){return ((a % MOD) + (b % MOD)) % MOD;}
- int board[505][505];
- int n,m;
- const int MX = 505*505 + 10000;
- int pp[MX];
- int par[MX];
- int lvl[MX];
- int sparse[MX][19];
- int sz[MX];
- void dfs(int curr ,int par = 0){
- lvl[curr] = lvl[par] + 1;
- sparse[curr][0] = par;
- for(int j : adj)
- }
- int findpar(int x){
- return (x == pp[x]) ? x: pp[x] = findpar(pp[x]);
- }
- vector<pair<int,int> > adj[MX];
- bool join(int a, int b){
- int pa = findpar(a);
- int pb = findpar(b);
- if(pa == pb) return 0;
- if(sz[b] > sz[a]){
- swap(a,b);
- }
- pp[b] = a;
- sz[a] += sz[b];
- return 1;
- }
- int indx(int i, int j){
- return i*n + j;
- }
- int dx[] = {1,-1,0,0};
- int dy[] = {0,0,1,-1};
- bool valid(int x, int y){
- return x >= 1 && x <= n && y>=1 && y<= m;
- }
- void getEdges(){
- vector<pair<int, pair<int,int> > > edges;
- for(int i = 1 ; i <= n ; i++){
- for(int j = 1; j <= m ; j++ ){
- for(int k = 0 ; k < 4 ; k++){
- int nx = i+dx[k];
- int ny = j+dy[k];
- if(valid(nx,ny)){
- int cost = max(board[i][j], board[nx][ny]);
- edges.push_back({cost,{indx(i,j), indx(nx, ny)});
- }
- }
- }
- }
- return edges;
- }
- int32_t main()
- {
- IO;
- cin >> n >> m >> q;
- for(int i = 1;i <= n;i++)
- {
- for(int j = 1;j <= m;j++)
- cin >> board[i][j];
- }
- vector<pair<int,pair<int,int> > > edges = getEdges();
- sort(all(edges));
- for(int i = 1 ; i<= MX ; i++) pp[i] = i;
- for(int i = 0 ;i < edges.size() ; i++){
- if(join(edges[i].se.f, edges[i].se.se)){
- adj[edges[i].se.f].push_back(edges[i].se.se);
- adj[edges[i].se.se].push_back(edges[i].se.f);
- }
- }
- dfs(n+1);
- /*vector<vector<int> > queries(q);
- for(int i = 0;i < q;i++)
- {
- int x1,y1,x2,y2;
- cin >> x1 >> y1 >> x2 >> y2;
- queries[i] = vector<int>{x1,y1,x2,y2,i};
- }*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement