fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll int
  3. #define pll pair<ll,ll>
  4. #define db long double
  5. #define foru(i,a,b) for(ll i=(a);i<=(b);i++)
  6. #define ford(i,a,b) for(ll i=(a);i>=(b);i--)
  7. #define ALL(a) (a).begin(),(a).end()
  8. #define ROUND(i) fixed<<setprecision(i)
  9. #define fi first
  10. #define se second
  11. using namespace std;
  12. int NumTest=1,CurTest;
  13. clock_t start_time_=clock();
  14. namespace fasstIO {
  15.     const int SZ = 1 << 20;
  16.     char in[SZ], out[SZ];
  17.     int ip = 0, len = 0, op = 0;
  18.  
  19.     inline char gc() {
  20.         if (ip == len) {
  21.             len = fread(in, 1, SZ, stdin);
  22.             ip = 0;
  23.             if (!len) return 0;
  24.         }
  25.         return in[ip++];
  26.     }
  27.  
  28.     inline int readInt() {
  29.         int x = 0, sign = 1;
  30.         char c = gc();
  31.         while (c <= ' ' && c) c = gc();
  32.         if (c == '-') sign = -1, c = gc();
  33.         while (c >= '0' && c <= '9') {
  34.             x = x * 10 + c - '0';
  35.             c = gc();
  36.         }
  37.         return x * sign;
  38.     }
  39.  
  40.     inline void flush() {
  41.         fwrite(out, 1, op, stdout);
  42.         op = 0;
  43.     }
  44.  
  45.     inline void writeInt(int x, char end = '\n') {
  46.         if (x < 0) out[op++] = '-', x = -x;
  47.         char s[12];
  48.         int n = 0;
  49.         do s[n++] = x % 10 + '0', x /= 10; while (x);
  50.         while (n--) {
  51.             if (op == SZ) flush();
  52.             out[op++] = s[n];
  53.         }
  54.         if (op == SZ) flush();
  55.         out[op++] = end;
  56.     }
  57.  
  58.     struct AutoFlush {
  59.         ~AutoFlush() { flush(); }
  60.     } autoFlush;
  61. }
  62. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  63. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣶⣾⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  64. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⡞⠀⠀⢀⣤⣴⣾⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⣀⠀⠀⠀⠀⠀⠀⠀
  65. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣶⣿⣿⣣⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣤⣶⣾⣿⠃⠀⠀⠀⠀⠀⠀⠀
  66. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⣀⣀⣀⡤⠀⠀⠀
  67. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀
  68. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
  69. ///⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀
  70. ///⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣤⣶⣾⡟⠀
  71. ///⠀⠀⠀⠀⠀⠀⡰⢹⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀
  72. ///⠀⠀⠀⠀⠀⢠⣳⣿⣾⣿⣿⣿⣿⢋⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀
  73. ///⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⡞⠀⠈⠙⠿⠿⠟⠛⠉⠀⠀⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠀⠀
  74. ///⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⡄⠀⠀⠀⠀⠀⠀⠐⡄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⠀
  75. ///⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⢿⣿⣿⠀⠀⡌ -TFA-⠀⠀ ⠀⢻⣿⣿⡇⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣴⡶⠋⠁
  76. ///⠀⠀⠀⠀⢸⣿⣿⣿⣿⡟⢻⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣼⣿⣿⠗⢺⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠀⠀⠀
  77. ///⠀⠀⠀⠀⢸⣿⣿⣿⣿⣇⣀⣻⣇⠈⣖⣄⠀⠀⠀⢀⡤⠖⣻⢍⣁⣀⣿⣏⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀
  78. ///⠀⠀⠀⠀⢸⡿⣿⣿⣿⡇⢻⢻⣿⣿⣶⡽⠂⠀⠀⠀⠀⢽⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣵⣶⠖⠋⠀⠀
  79. ///⠀⠀⠀⠀⢸⡇⢸⣿⣿⣿⡈⠘⢛⣿⢿⡇⠀⠀⠀⠀⠀⠈⠡⠼⠏⣻⣿⡿⢻⠏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀
  80. ///⠀⠀⠀⠀⢸⠁⠈⣿⣿⣿⡇⠈⠪⠷⠚⠁⠀⠀⠀⠀⠀⠀⠀⠀⠈⠽⠷⠞⠃⠀⢸⣿⣿⣿⣿⢏⣿⣿⣿⡟⠁⠀⠀⠀⠀⠀⠀
  81. ///⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣷⠀⠀⠀⠀⠀⠀⢀⢠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⢸⣿⣿⣿⣏⣡⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠀
  82. ///⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⠃⢸⣿⣿⣿⣿⣿⡟⠀⠉⠛⠣⠀⠀⠀⠀⠀⠀
  83. ///⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⡟⠙⠢⣄⠀⠀⠀⠒⢂⠠⠀⠀⠀⠀⠀⠀⢈⡠⠔⢻⣿⣿⡟⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  84. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡿⠇⠀⠀⡨⠋⢲⠤⣀⠈⠀⢀⣀⡀⠤⢖⠞⠉⠀⠀⢸⡟⠻⣄⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  85. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡇⠀⡠⠊⠐⡄⠀⠀⡀⠉⠉⠉⠀⠀⢀⠎⠀⠀⠀⠀⠟⠀⠀⠈⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  86. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡁⠀⠀⠁⣆⠏⠈⢓⠒⠋⠁⣄⠞⠀⠀⠀⠀⠀⠀⠐⢈⡤⠒⠛⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  87. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⡻⣠⠀⠀⠀⡿⠀⠀⠀⠀⠀⠀⡜⠀⠀⠀⠀⠀⠀⠀⡴⠋⠀⠳⡀⠸⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  88. ///⠀⠀⠀⠀⠀⠀⠀⠀⠀⡜⠁⠀⡟⠀⠀⠀⡇⠀⠀⠀⠀⠀⢰⠁⠀⠀⠀⠀⠀⢀⠜⠀⠀⠀⠀⠀⠀⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀
  89. ///⠀⠀⠀⠀⠀⠀⣀⠠⠞⠀⠀⢀⠇⠀⠀⠀⡇⠀⠀⠀⠀⢀⡆⠀⠀⠀⠀⠀⠀⡌⠀⢀⠂⠀⠀⠀⠀⠈⡄⠀⠀⠀⠀⠀⠀⠀⠀
  90. ///⠀⠀⠀⣠⠔⠊⠁⠀⠀⠀⠀⢸⠀⠀⠀⠀⡇⠀⠀⠀⠀⡜⠀⠀⠀⠀⠀⠀⠀⡇⠀⡜⠀⠀⠀⠀⠀⠀⢹⡀⠀⠀⠀⠀⠀⠀⠀
  91. ///⣠⣖⠉⠁⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀⠀⠀⢰⣀⡀⠀⡼⠀⠀⠀⠒⠀⠀⠠⠂⠇⢠⠁⠀⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀
  92. ///⠸⣟⣿⡇⠀⠀⠀⠀⠀⠀⢠⣷⣖⡒⣆⠀⢲⣷⣉⠞⣠⠖⠒⠒⠲⢤⣤⣀⣀⣰⡜⠀⠀⠀⠀⠀⠀⠀⠀⠸⡄⠀⠀⠀⠀⠀⠀
  93. ///⠀⠀⠈⢹⡀⠀⠀⠀⠀⠀⠀⢹⣽⣒⣼⣿⣿⣿⣧⡞⠓⠒⠀⢀⣴⣯⣾⣷⡘⢻⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀
  94. const ll dx[]={+1,0,-1,0};
  95. const ll dy[]={0,-1,0,+1};
  96. ll n,m,q;
  97. bool g[505][505];
  98. pll opt[2500005];
  99. ll par[2500005];
  100. ll last[505][505];
  101. ll id[505][505],k=0;
  102. ll headq[2500005],nxtq[2500005],arrq[2500005],szq=0;
  103. ll headc[2500005],nxtc[2500005],arrc[2500005],szc=0;
  104. ll finish[20005];
  105. ll result=0;
  106.  
  107. bool valid(ll x,ll y){
  108. 	return 1<=x && x<=n && 1<=y && y<=m && g[x][y]==1;
  109. }
  110. void prebuild(){
  111. 	memset(last,0x3f,sizeof(last));
  112. 	ford(i,q,1){
  113. 		auto [x,y]=opt[i];
  114. 		par[i]=q+1;
  115. 		foru(e,0,3){
  116. 			ll nx=x+dx[e], ny=y+dy[e];
  117.  
  118. 			if(valid(nx,ny)){
  119. 				par[i]=min(par[i],last[nx][ny]);
  120. 			}
  121. 		}
  122. 		arrc[++szc]=i; nxtc[szc]=headc[par[i]]; headc[par[i]]=szc;
  123. 		last[x][y]=i;
  124. 	}	
  125.  
  126. 	foru(i,1,n)foru(j,1,m)if(g[i][j]==1){
  127. 		id[i][j]=++k;
  128. 		ll to=q+1;
  129. 		foru(e,0,3){
  130. 			ll nx=i+dx[e], ny=j+dy[e];
  131. 			if(valid(nx,ny))to=min(to,last[nx][ny]);
  132. 		}
  133. 		arrq[++szq]=k; nxtq[szq]=headq[to]; headq[to]=szq;
  134. 	}
  135.  
  136.  
  137. }
  138.  
  139. void DFS(ll u){
  140. 	stack<pll>stk;
  141. 	stk.push({u,-1});
  142.  
  143. 	while(stk.size()){
  144. 		auto[u,t]=stk.top(); stk.pop();
  145.  
  146. 		if(t!=-1){
  147. 			finish[u]=t;
  148. 			continue;
  149. 		}
  150.  
  151. 		ll p=id[opt[u].fi][opt[u].se];
  152. 		ll old=finish[p];
  153. 		finish[p]=u;
  154.  
  155. 		int j=headq[u];
  156. 		while(j){
  157. 			int p=arrq[j]; j=nxtq[j];
  158. 			foru(x,1,k)if(x!=p)result=max(result,finish[x]);
  159. 		}
  160.  
  161. 		stk.push({p,old});
  162.  
  163. 		int i=headc[u];
  164. 		while(i){
  165. 			ll v=arrc[i]; i=nxtc[i];
  166. 			stk.push({v,-1});
  167. 		}
  168.  
  169. 	}
  170.  
  171.  
  172. }
  173.  
  174.  
  175. void Uchiha_Sasuke(){
  176. 	n=fasstIO::readInt();
  177. 	m=fasstIO::readInt();
  178. 	foru(i,1,n)foru(j,1,m)g[i][j]=fasstIO::readInt();
  179. 	q=fasstIO::readInt();
  180. 	foru(i,1,q) {
  181. 	    opt[i].fi=fasstIO::readInt();
  182. 	    opt[i].se=fasstIO::readInt();
  183. 	}
  184.  
  185. 	prebuild();
  186. 	DFS(q+1);
  187.  
  188. 	cout<<result<<'\n';
  189. }
  190.  
  191. signed main(){
  192.     // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  193.     if(fopen("task.inp","r"))
  194.     freopen("task.inp","r",stdin),
  195.     freopen("task.out","w",stdout);
  196.     srand(time(0));
  197.  
  198.     //cin>>NumTest;
  199.     for(CurTest=1;CurTest<=NumTest;CurTest++)Uchiha_Sasuke();
  200.  
  201.  
  202.     clock_t finish_time_=clock();
  203.     double run_time_=((double)finish_time_-(double)start_time_)/CLOCKS_PER_SEC;
  204.     cerr<<"\n\n------------------------------------------------\nRun Time : "<<fixed<<setprecision(3)<<run_time_<<"s\n\n";
  205.  
  206.     return 0;
  207. }
  208.  
Success #stdin #stdout #stderr 0s 5968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 

------------------------------------------------
Run Time : 0.000s
https://ideone.com/xaGhKR
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

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!