fork(2) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-8
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. #define dbl long double
  28. using namespace std;
  29. // mylittledoge
  30.  
  31. int gcd(int x, int y) {
  32.     if(x > y) swap(x,y);
  33.     while(x > 0) {
  34.         int z =x;
  35.         x =y%x;
  36.         y =z;}
  37.     return y;}
  38.  
  39. int main() {
  40.     cin.sync_with_stdio(0);
  41.     cin.tie(0);
  42.     int N;
  43.     cin >> N;
  44.     vector< vector<int> > H(N,vector<int>(N));
  45.     vector< vector<int> > V =H;
  46.     for(int i =0; i < N*N; i++) cin >> H[i/N][i%N];
  47.     for(int i =0; i < N*N; i++) cin >> V[i/N][i%N];
  48.  
  49.     queue< pair<int,int> > q;
  50.     int dx[] ={1,-1,0,0};
  51.     int dy[] ={0,0,1,-1};
  52.     int C =0;
  53.     vector< vector<int> > isC(N,vector<int>(N,-1));
  54.     vector<int> sC;
  55.     for(int i =0; i < N; i++) for(int j =0; j < N; j++) if(isC[i][j] == -1) {
  56.         q.push(make_pair(i,j));
  57.         isC[i][j] =C;
  58.         int s =1;
  59.         while(!q.empty()) {
  60.             int x =q.front().ff, y =q.front().ss;
  61.             for(int k =0; k < 4; k++) if(max(dx[k]+x,dy[k]+y) < N && min(dx[k]+x,dy[k]+y) >= 0)
  62.                 if(isC[dx[k]+x][dy[k]+y] == -1 && V[x][y] == V[dx[k]+x][dy[k]+y] && H[x][y] == H[dx[k]+x][dy[k]+y]) {
  63.                     isC[dx[k]+x][dy[k]+y] =C;
  64.                     s++;
  65.                     q.push(make_pair(dx[k]+x,dy[k]+y));}
  66.             q.pop();}
  67.         sC.push_back(s);
  68.         C++;}
  69.  
  70.     map< pair<int,int>, int> T;
  71.     vector< vector< pair<int,int> > > G0;
  72.     G0.dibs(100000);
  73.     for(int i =0; i < N; i++) for(int j =0; j < N; j++) for(int k =0; k < 4; k++)
  74.         if(max(dx[k]+i,dy[k]+j) < N && min(dx[k]+i,dy[k]+j) >= 0)
  75.             if(isC[i][j] != isC[i+dx[k]][j+dy[k]]) {
  76.                 int a =H[i][j]-H[i+dx[k]][j+dy[k]];
  77.                 int b =-V[i][j]+V[i+dx[k]][j+dy[k]];
  78.                 if(b == 0) continue;
  79.                 if(b < 0) a *=-1, b *=-1;
  80.                 int d =gcd(abs(a),b);
  81.                 if(a < 0) continue;
  82.                 int t =(T.find(make_pair(a/d,b/d)) == T.end())?T.size():T[make_pair(a/d,b/d)];
  83.                 T[make_pair(a/d,b/d)] =t;
  84. 				G0.resize(max((int)G0.size(),t+1));
  85. 				G0[t].push_back(make_pair(isC[i][j],isC[i+dx[k]][j+dy[k]]));}
  86.  
  87.     int ans =0;
  88.     queue<int> qq;
  89.     vector<bool> vis(C,false);
  90.     vector< vector<int> > G(C);
  91. 	vector<int> vv;
  92. 	for(int t =0; t < G0.size(); t++) {
  93. 	    ALL_THE(G0[t],jt) {
  94.    			G[jt->ff].push_back(jt->ss);
  95.    			G[jt->ss].push_back(jt->ff);}
  96.    		ALL_THE(G0[t],jt) if(!vis[jt->ff]) {
  97.    			int akt =0;
  98.    			qq.push(jt->ff);
  99. 	   		vis[qq.front()] =true;
  100.     		while(!qq.empty()) {
  101.     			akt +=sC[qq.front()];
  102.     			vv.push_back(qq.front());
  103.     			ALL_THE(G[qq.front()],kt) if(!vis[*kt]) {
  104.     				vis[*kt] =true;
  105.     				qq.push(*kt);}
  106.     			qq.pop();}
  107.     		ans =max(ans,akt);}
  108.     	ALL_THE(G0[t],jt) {
  109.     		G[jt->ff].clear();
  110.     		G[jt->ss].clear();}
  111.     	ALL_THE(vv,jt) vis[*jt] =false;
  112.     	vv.clear();}
  113.  
  114.     cout << ans << "\n";
  115.     return 0;}
  116.  
  117. // look at my code
  118. // my code is amazing
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3
stdout
copy 
7
https://ideone.com/wX7J6h
COCI SUMA
language:
C++14 (gcc 8.3)
created:
10 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!