A. Hard to prepare
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e5+10; 25 26 /** 27 0: x1<>xn and x1<>~xn 28 1: x1=xn 29 2: x1=~xn 30 **/ 31 32 ll a[3][3],b[3][3],c[3][3]; 33 34 ll mul(ll x,ll y) 35 { 36 ll r=1; 37 while (y) 38 { 39 if (y & 1) 40 r=r*x%mod; 41 x=x*x%mod; 42 y>>=1; 43 } 44 return r; 45 } 46 47 int main() 48 { 49 int t,n,i,j,k; 50 ll z,v,vv,r; 51 52 53 scanf("%d",&t); 54 while (t--) 55 { 56 scanf("%d%lld",&n,&z); 57 if (z==1) 58 { 59 printf("2 "); 60 continue; 61 } 62 v=mul(2,z); 63 if (n==1) 64 { 65 printf("%lld ",v); 66 continue; 67 } 68 69 for (i=0;i<3;i++) 70 for (j=0;j<3;j++) 71 a[i][j]=0; 72 a[1][0]=a[1][1]=a[2][0]=a[2][2]=1; 73 a[0][0]=v-3; 74 a[0][1]=v-2; 75 a[0][2]=v-2; 76 77 for (i=0;i<3;i++) 78 for (j=0;j<3;j++) 79 b[i][j]=0; 80 for (i=0;i<3;i++) 81 b[i][i]=1; 82 83 n-=2; 84 while (n) 85 { 86 if (n & 1) 87 { 88 for (i=0;i<3;i++) 89 for (j=0;j<3;j++) 90 { 91 c[i][j]=b[i][j]; 92 b[i][j]=0; 93 } 94 for (i=0;i<3;i++) 95 for (j=0;j<3;j++) 96 for (k=0;k<3;k++) 97 b[i][j]=(b[i][j]+a[i][k]*c[k][j])%mod; 98 } 99 n>>=1; 100 101 for (i=0;i<3;i++) 102 for (j=0;j<3;j++) 103 { 104 c[i][j]=a[i][j]; 105 a[i][j]=0; 106 } 107 for (i=0;i<3;i++) 108 for (j=0;j<3;j++) 109 for (k=0;k<3;k++) 110 a[i][j]=(a[i][j]+c[i][k]*c[k][j])%mod; 111 } 112 113 r=0; 114 vv=v*(v-2)%mod; 115 printf("%lld ",( 116 vv*(b[0][0]+b[1][0])%mod 117 +v*(b[0][1]+b[1][1])%mod 118 +mod)%mod); 119 } 120 return 0; 121 } 122 /* 123 5 2 124 244 125 126 1 3 127 8 128 129 2 3 130 56 131 132 3 3 133 344 134 135 4 3 136 2408 137 138 1 5 139 32 140 141 2 5 142 992 143 144 3 5 145 29792 146 */
testA
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e5+10; 25 26 int n=2; 27 int k=31;///2^z-1 28 int a[maxn]; 29 int tot=0; 30 31 void dfs(int index) 32 { 33 int i; 34 if (index==n+1) 35 { 36 if (a[n]+a[1]!=k) 37 { 38 // for (i=1;i<=n;i++) 39 // printf("%d ",a[i]); 40 // printf(" "); 41 tot++; 42 } 43 return; 44 } 45 for (i=0;i<=k;i++) 46 if (i+a[index-1]!=k) 47 { 48 a[index]=i; 49 dfs(index+1); 50 } 51 } 52 53 int main() 54 { 55 a[0]=-10000; 56 dfs(1); 57 printf("%d",tot); 58 return 0; 59 } 60 /* 61 5 2 62 244 63 64 1 3 65 8 66 67 2 3 68 56 69 70 3 3 71 344 72 73 4 3 74 2408 75 76 1 5 77 32 78 79 2 5 80 992 81 82 3 5 83 29792 84 */
B. BE, GE or NE
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e3+10; 25 const int maxm=2e2+10; 26 27 int f[maxn][maxm],dif=100,n,l,r; 28 int a[maxn],b[maxn],c[maxn],last[maxm]; 29 30 void dfs(int i,int x) 31 { 32 int y; 33 34 if (a[i]!=0) 35 { 36 y=min(x+a[i],100); 37 if (i==n) 38 f[i+1][y+dif]=last[y+dif]; 39 else if (f[i+1][y+dif]==-2 || f[i+1][y+dif]==2) 40 dfs(i+1,y); 41 if (i & 1) 42 f[i][x+dif]=max(f[i][x+dif],f[i+1][y+dif]); 43 else 44 f[i][x+dif]=min(f[i][x+dif],f[i+1][y+dif]); 45 } 46 if (b[i]!=0) 47 { 48 y=max(x-b[i],-100); 49 if (i==n) 50 f[i+1][y+dif]=last[y+dif]; 51 else if (f[i+1][y+dif]==-2 || f[i+1][y+dif]==2) 52 dfs(i+1,y); 53 if (i & 1) 54 f[i][x+dif]=max(f[i][x+dif],f[i+1][y+dif]); 55 else 56 f[i][x+dif]=min(f[i][x+dif],f[i+1][y+dif]); 57 } 58 if (c[i]!=0) 59 { 60 y=-x; 61 if (i==n) 62 f[i+1][y+dif]=last[y+dif]; 63 else if (f[i+1][y+dif]==-2 || f[i+1][y+dif]==2) 64 dfs(i+1,y); 65 if (i & 1) 66 f[i][x+dif]=max(f[i][x+dif],f[i+1][y+dif]); 67 else 68 f[i][x+dif]=min(f[i][x+dif],f[i+1][y+dif]); 69 } 70 } 71 72 int main() 73 { 74 int m,i,j; 75 scanf("%d%d%d%d",&n,&m,&r,&l); 76 for (i=1;i<=n;i++) 77 scanf("%d%d%d",&a[i],&b[i],&c[i]); 78 ///Koutarou first max 79 for (i=1;i<=n;i++) 80 for (j=0;j<=200;j++) 81 if (i & 1) ///max 82 f[i][j]=-2; 83 else 84 f[i][j]=2; 85 86 for (i=0;i<=l+100;i++) 87 last[i]=-1; 88 for (i=r+100;i<=200;i++) 89 last[i]=1; 90 91 dfs(1,m); 92 93 if (f[1][m+dif]==1) 94 printf("Good Ending"); 95 else if (f[1][m+dif]==-1) 96 printf("Bad Ending"); 97 else 98 printf("Normal Ending"); 99 return 0; 100 }
C. Cacti Lottery
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e6+10; 25 26 int n=9,z[10]; 27 struct node 28 { 29 int a[10],price; 30 int each[8]; 31 }f[maxn],cur; 32 bool vis[10]; 33 char s[20]; 34 int award[30]; 35 int number=362880; 36 int tot_know,tot_num,pos[maxn],each[8]; 37 int x,xx; 38 ll y; 39 double yy=0; 40 41 void DFS(int j) 42 { 43 int i; 44 if (j==n+1) 45 { 46 int value=0,k; 47 memset(vis,0,sizeof(vis)); 48 for (i=1;i<=n;i++) 49 { 50 k=0; 51 for (j=1;j<cur.a[i];j++) 52 if (!vis[j]) 53 k++; 54 value+=k*z[n-i]; 55 vis[cur.a[i]]=1; 56 } 57 f[value]=cur; 58 f[value].each[0]=award[ cur.a[1]+cur.a[4]+cur.a[7] ]; 59 f[value].each[1]=award[ cur.a[2]+cur.a[5]+cur.a[8] ]; 60 f[value].each[2]=award[ cur.a[3]+cur.a[6]+cur.a[9] ]; 61 f[value].each[3]=award[ cur.a[1]+cur.a[2]+cur.a[3] ]; 62 f[value].each[4]=award[ cur.a[4]+cur.a[5]+cur.a[6] ]; 63 f[value].each[5]=award[ cur.a[7]+cur.a[8]+cur.a[9] ]; 64 f[value].each[6]=award[ cur.a[1]+cur.a[5]+cur.a[9] ]; 65 f[value].each[7]=award[ cur.a[3]+cur.a[5]+cur.a[7] ]; 66 67 f[value].price= 68 max( 69 max(max(f[value].each[0],f[value].each[1]), 70 max(f[value].each[2],f[value].each[3])), 71 max(max(f[value].each[4],f[value].each[5]), 72 max(f[value].each[6],f[value].each[7])) ); 73 return ; 74 } 75 76 for (i=j;i<=n;i++) 77 { 78 swap(cur.a[j],cur.a[i]); 79 DFS(j+1); 80 swap(cur.a[j],cur.a[i]); 81 } 82 } 83 84 void init() 85 { 86 award[6]= 10000; 87 award[7]= 36; 88 award[8]= 720; 89 award[9]= 360; 90 award[10]= 80; 91 award[11]= 252; 92 award[12]= 108; 93 award[13]= 72; 94 award[14]= 54; 95 award[15]= 180; 96 award[16]= 72; 97 award[17]= 180; 98 award[18]= 119; 99 award[19]= 36; 100 award[20]= 360; 101 award[21]= 1080; 102 award[22]= 144; 103 award[23]= 1800; 104 award[24]= 3600; 105 cur.price=0; 106 } 107 108 /** 109 * :konw 110 # :don't konw 111 **/ 112 113 void dfs2(int j) 114 { 115 int i; 116 if (j==tot_num+1) 117 { 118 int value=0,k; 119 memset(vis,0,sizeof(vis)); 120 for (i=1;i<=n;i++) 121 { 122 k=0; 123 for (j=1;j<cur.a[i];j++) 124 if (!vis[j]) 125 k++; 126 value+=k*z[n-i]; 127 vis[cur.a[i]]=1; 128 } 129 130 for (i=0;i<8;i++) 131 each[i]+=f[value].each[i]; 132 x++; 133 return ; 134 } 135 136 for (i=j;i<=tot_num;i++) 137 { 138 swap(cur.a[pos[j]],cur.a[pos[i]]); 139 dfs2(j+1); 140 swap(cur.a[pos[j]],cur.a[pos[i]]); 141 } 142 } 143 144 void dfs1(int j) 145 { 146 int i; 147 if (j==tot_know+1) 148 { 149 memset(each,0,sizeof(each)); 150 x=0; 151 dfs2(j); 152 y= 153 max( 154 max(max(each[0],each[1]), 155 max(each[2],each[3])), 156 max(max(each[4],each[5]), 157 max(each[6],each[7])) ); 158 159 xx++; 160 yy+=1.0*y/x; 161 ///add have 10000 ... exit directly 162 return ; 163 } 164 165 for (i=j;i<=tot_num;i++) 166 { 167 swap(cur.a[pos[j]],cur.a[pos[i]]); 168 dfs1(j+1); 169 swap(cur.a[pos[j]],cur.a[pos[i]]); 170 } 171 } 172 173 int main() 174 { 175 int t,i,j; 176 177 init(); 178 z[1]=1; 179 for (i=2;i<=9;i++) 180 z[i]=z[i-1]*i; 181 182 for (i=1;i<=9;i++) 183 cur.a[i]=i; 184 185 DFS(1); 186 187 scanf("%d",&t); 188 while (t--) 189 { 190 scanf("%s",s+1); 191 scanf("%s",s+4); 192 scanf("%s",s+7); 193 194 memset(vis,0,sizeof(vis)); 195 x=0,y=0; 196 tot_know=0; 197 for (i=1;i<=9;i++) 198 if (s[i]>='1' && s[i]<='9') 199 { 200 cur.a[i]=s[i]-48; 201 vis[cur.a[i]]=1; 202 } 203 else if (s[i]=='*') 204 { 205 tot_know++; 206 pos[tot_know]=i; 207 } 208 209 tot_num=tot_know; 210 for (i=1;i<=9;i++) 211 if (s[i]=='#') 212 { 213 tot_num++; 214 pos[tot_num]=i; 215 } 216 217 for (i=1;i<=9;i++) 218 if (s[i]=='#' || s[i]=='*') 219 { 220 for (j=1;j<=9;j++) 221 if (!vis[j]) 222 break; 223 cur.a[i]=j; 224 vis[j]=1; 225 } 226 227 xx=0; 228 yy=0; 229 dfs1(1); 230 231 printf("%.10f ",1.0*yy/xx); 232 } 233 return 0; 234 } 235 /* 236 2 237 *** 238 *** 239 *** 240 241 ##* 242 #*# 243 *## 244 */
F. Features Track
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e5+10; 25 26 struct node 27 { 28 int x,y,z; 29 }f[maxn]; 30 31 int cmp(node a,node b) 32 { 33 if (a.x<b.x) 34 return 1; 35 else if (a.x>b.x) 36 return 0; 37 if (a.y<b.y) 38 return 1; 39 else if (a.y>b.y) 40 return 0; 41 if (a.z<b.z) 42 return 1; 43 else 44 return 0; 45 } 46 47 int main() 48 { 49 int t,n,m,i,j,k,r; 50 scanf("%d",&t); 51 while (t--) 52 { 53 scanf("%d",&n); 54 j=0; 55 for (i=1;i<=n;i++) 56 { 57 scanf("%d",&m); 58 while (m--) 59 { 60 j++; 61 scanf("%d%d",&f[j].x,&f[j].y); 62 f[j].z=i; 63 } 64 } 65 sort(f+1,f+j+1,cmp); 66 67 r=0; 68 f[j+1].x=f[j].x-1; 69 k=1; 70 for (i=1;i<=j;i++) 71 { 72 if (f[i].x==f[i+1].x && f[i].y==f[i+1].y) 73 { 74 if (f[i].z==f[i+1].z) 75 continue; 76 else if (f[i].z==f[i+1].z-1) 77 { 78 k++; 79 continue; 80 } 81 } 82 r=max(r,k); 83 k=1; 84 } 85 printf("%d ",r); 86 } 87 return 0; 88 } 89 /* 90 3 91 92 8 93 2 1 1 2 2 94 2 1 1 1 4 95 2 1 1 2 2 96 2 2 2 1 4 97 0 98 0 99 1 1 1 100 1 1 1 101 102 5 103 1 1 1 104 2 2 2 1 1 105 3 1 1 1 1 1 1 106 1 2 3 107 1 1 1 108 109 5 110 1 1 1 111 2 2 2 1 3 112 3 1 1 1 1 1 1 113 1 2 3 114 1 1 1 115 */
G. Trace
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=5e4+10; 25 26 struct node 27 { 28 int v,num; 29 }x[maxn],y[maxn]; 30 31 struct rec 32 { 33 int x,y; 34 }ff[maxn],f[maxn]; 35 36 int vx[maxn],vy[maxn],s[maxn]; 37 38 int cmp1(node a,node b) 39 { 40 return a.v>b.v; 41 } 42 43 int main() 44 { 45 int n,i,j,value; 46 ll sum=0; 47 48 scanf("%d",&n); 49 // for (i=1;i<=n;i++) 50 for (i=n;i>=1;i--) 51 scanf("%d%d",&ff[i].x,&ff[i].y); 52 ff[0]={-1,-1}; 53 54 55 memset(s,0,sizeof(s)); 56 for (i=1;i<=n;i++) 57 { 58 x[i].num=i; 59 x[i].v=ff[i].x; 60 } 61 sort(x+1,x+n+1,cmp1); 62 j=0; 63 for (i=1;i<=n;i++) 64 { 65 if (ff[i].x!=ff[i-1].x) 66 { 67 j++; 68 vx[j]=ff[i].x; 69 } 70 f[x[i].num].x=j; 71 f[x[i].num].y=ff[x[i].num].y; 72 } 73 for (i=1;i<=n;i++) 74 { 75 value=0; 76 j=f[i].x-1; 77 while (j>0) 78 { 79 value=max(value,s[j]); 80 j-=(j & (-j)); 81 } 82 83 sum+=f[i].y-value; 84 85 j=f[i].x; 86 while (j<=n) 87 { 88 s[j]=max(s[j],f[i].y); 89 j+=(j & (-j)); 90 } 91 } 92 93 94 ///==========/// 95 ///y lisan 96 memset(s,0,sizeof(s)); 97 for (i=1;i<=n;i++) 98 { 99 y[i].num=i; 100 y[i].v=ff[i].y; 101 } 102 sort(y+1,y+n+1,cmp1); 103 j=0; 104 for (i=1;i<=n;i++) 105 { 106 if (ff[i].y!=ff[i-1].y) 107 { 108 j++; 109 vy[j]=ff[i].y; 110 } 111 f[y[i].num].y=j; 112 f[y[i].num].x=ff[y[i].num].x; 113 } 114 for (i=1;i<=n;i++) 115 { 116 value=0; 117 j=f[i].y-1; 118 while (j>0) 119 { 120 value=max(value,s[j]); 121 j-=(j & (-j)); 122 } 123 124 sum+=f[i].x-value; 125 126 j=f[i].y; 127 while (j<=n) 128 { 129 s[j]=max(s[j],f[i].x); 130 j+=(j & (-j)); 131 } 132 } 133 134 printf("%lld",sum); 135 136 return 0; 137 } 138 /* 139 3 140 1 4 141 3 3 142 4 1 143 144 2 145 1 4 146 4 1 147 */
H. Ryuji doesn't want to study
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e5+10; 25 26 ll x[maxn],y[maxn],s[maxn]; 27 28 int main() 29 { 30 int n,q,i,j,a,b,c; 31 ll sum; 32 scanf("%d%d",&n,&q); 33 for (i=1;i<=n;i++) 34 { 35 scanf("%d",&s[i]); 36 j=i; 37 while (j<=n) 38 { 39 x[j]+=s[i]; 40 y[j]+=1ll*s[i]*(n-i); 41 j+=(j & (-j)); 42 } 43 } 44 45 while (q--) 46 { 47 scanf("%d%d%d",&a,&b,&c); 48 if (a==1) 49 { 50 sum=0; 51 j=c; 52 while (j>0) 53 { 54 sum+=y[j]-x[j]*(n-c-1); 55 j-=(j & (-j)); 56 } 57 j=b-1; 58 while (j>0) 59 { 60 sum-=y[j]-x[j]*(n-c-1); 61 j-=(j & (-j)); 62 } 63 printf("%lld ",sum); 64 } 65 else 66 { 67 j=b; 68 while (j<=n) 69 { 70 x[j]-=s[b]; 71 y[j]-=s[b]*(n-b); 72 j+=(j & (-j)); 73 } 74 75 j=b; 76 while (j<=n) 77 { 78 x[j]+=c; 79 y[j]+=1ll*c*(n-b); 80 j+=(j & (-j)); 81 } 82 s[b]=c; 83 } 84 } 85 return 0; 86 } 87 /* 88 5 5 89 1 2 3 4 5 90 1 2 5 91 2 3 -1 92 1 2 5 93 */
I. Characters with Hash
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define nl 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=1e6+10; 25 26 char str[maxn]; 27 28 int main() 29 { 30 // printf("%d ",'z'-'o'); 31 // printf("%d ",'z'-'M'); 32 // printf("%d ",'z'-'l'); 33 int t,len,v,i; 34 char c; 35 scanf("%d",&t); 36 while (t--) 37 { 38 scanf("%d %c",&len,&c); 39 scanf("%s",str); 40 41 for (i=0;i<len;i++) 42 if (str[i]!=c) 43 break; 44 if (i!=len && abs(c-str[i])<10) 45 v=1; 46 else 47 v=0; 48 printf("%d ",max(len*2-i*2-v,1)); 49 } 50 return 0; 51 }
J. Maze Designer
1 /* 2 打通n*m-1个相邻的格子。 3 树：格子相当于一个点，相邻直接连通的格子有一条边 4 删去树的边，使用剩下的边， 5 所以使用最大生成树 6 */ 7 #include <cstdio> 8 #include <cstdlib> 9 #include <cmath> 10 #include <cstring> 11 #include <time.h> 12 #include <string> 13 #include <set> 14 #include <map> 15 #include <list> 16 #include <stack> 17 #include <queue> 18 #include <vector> 19 #include <bitset> 20 #include <ext/rope> 21 #include <algorithm> 22 #include <iostream> 23 using namespace std; 24 #define ll long long 25 #define minv 1e-6 26 #define inf 1e9 27 #define pi 3.1415926536 28 #define nl 2.7182818284 29 const ll mod=1e9+7;//998244353 30 const int maxn=5e2+10; 31 const int maxt=maxn*maxn; 32 const int maxq=1e5+10; 33 34 struct rec 35 { 36 int x,y,z; 37 }e[maxt*4]; 38 39 struct node 40 { 41 int d,num; 42 node *next; 43 }*ask[maxt]; 44 45 int z[maxt][5],fa[maxt],dist[maxt],rd[maxq]; 46 bool vis[maxt]; 47 48 int getfather(int d) 49 { 50 if (fa[d]==d) 51 return d; 52 fa[d]=getfather(fa[d]); 53 return fa[d]; 54 } 55 56 void merge(int x,int y) 57 { 58 x=getfather(x); 59 y=getfather(y); 60 fa[y]=x; 61 } 62 63 void dfs(int d) 64 { 65 int i,dd; 66 node *r=ask[d]; 67 vis[d]=1; 68 for (i=1;i<=z[d][0];i++) 69 { 70 dd=z[d][i]; 71 if (!vis[dd]) 72 { 73 dist[dd]=dist[d]+1; 74 dfs(dd); 75 merge(d,dd); 76 } 77 } 78 while (r) 79 { 80 dd=r->d; 81 if (vis[dd]) 82 rd[r->num]=dist[d]+dist[dd]-2*dist[getfather(dd)]; 83 r=r->next; 84 } 85 } 86 87 int cmp(rec a,rec b) 88 { 89 return a.z>b.z; 90 } 91 92 int main() 93 { 94 int n,m,q,Q,x,y,g=0,num,i,j,a,b,c,d,d1,d2; 95 char c1,c2; 96 node *p; 97 scanf("%d%d ",&n,&m); 98 99 g=0; 100 num=0; 101 for (i=0;i<n;i++) 102 for (j=0;j<m;j++) 103 { 104 scanf("%c %d %c %d ",&c1,&d1,&c2,&d2); 105 if (c1=='D') 106 { 107 e[++g].x=num; 108 e[g].y=num+m; 109 e[g].z=d1; 110 } 111 112 if (c2=='R') 113 { 114 e[++g].x=num; 115 e[g].y=num+1; 116 e[g].z=d2; 117 } 118 119 num++; 120 } 121 sort(e+1,e+g+1,cmp); 122 123 for (i=0;i<n*m;i++) 124 fa[i]=i; 125 j=n*m-1; 126 for (i=1;j;i++) 127 { 128 while (1) 129 { 130 x=getfather(e[i].x); 131 y=getfather(e[i].y); 132 if (x!=y) 133 break; 134 i++; 135 } 136 137 fa[x]=y; 138 j--; 139 140 z[e[i].x][0]++; 141 z[e[i].x][z[e[i].x][0]]=e[i].y; 142 143 144 z[e[i].y][0]++; 145 z[e[i].y][z[e[i].y][0]]=e[i].x; 146 } 147 148 scanf("%d",&q); 149 for (Q=1;Q<=q;Q++) 150 { 151 scanf("%d%d%d%d",&a,&b,&c,&d); 152 a--,b--,c--,d--; 153 154 a=a*m+b; 155 c=c*m+d; 156 157 p=new node(); 158 p->d=c; 159 p->num=Q; 160 p->next=ask[a]; 161 ask[a]=p; 162 163 p=new node(); 164 p->d=a; 165 p->num=Q; 166 p->next=ask[c]; 167 ask[c]=p; 168 } 169 170 for (i=0;i<n*m;i++) 171 fa[i]=i; 172 dfs(0); 173 174 for (i=1;i<=q;i++) 175 printf("%d ",rd[i]); 176 return 0; 177 }