結果
| 問題 | No.3599 Queen Moving Query |
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2026-07-24 23:06:48 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 19,070 bytes |
| 記録 | |
| コンパイル時間 | 2,466 ms |
| コンパイル使用メモリ | 271,048 KB |
| 実行使用メモリ | 184,228 KB |
| 最終ジャッジ日時 | 2026-07-24 23:07:24 |
| 合計ジャッジ時間 | 9,643 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 16 WA * 10 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//だるすぎ.
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int H,W,sx,sy; cin >> H >> W >> sx >> sy,sx--,sy--;
vector<string> S(H);
for(auto &s : S) cin >> s;
int N = H*W;
vector<vector<pair<int,bool>>> Graph(N+N);
int n = Graph.size();
{
vector<pair<int,int>> D1(H);
for(int i=0; i<H; i++){
int s = W,siz = 1;
while(siz < s) siz += siz;
D1.at(i) = {siz,n};
if(siz == 1) continue;
for(int k=0; k<siz+siz; k++) Graph.push_back({});
for(int k=1; k<siz; k++){
if(k+k >= siz){
int left = k+k-siz,right = k+k-siz+1;
if(left < W) Graph.at(n+k).push_back({i*W+left,0});
if(right < W) Graph.at(n+k).push_back({i*W+right,0});
}
else{
int left = k+k,right = k+k+1;
Graph.at(n+k).push_back({n+left,0});
Graph.at(n+k).push_back({n+right,0});
}
}
n += siz;
for(int k=1; k<siz; k++){
if(k+k >= siz){
int left = k+k-siz,right = k+k-siz+1;
if(left < W) Graph.at(n+k).push_back({i*W+left+N,0});
if(right < W) Graph.at(n+k).push_back({i*W+right+N,0});
}
else{
int left = k+k,right = k+k+1;
Graph.at(n+k).push_back({n+left,0});
Graph.at(n+k).push_back({n+right,0});
}
}
n += siz;
}
vector<vector<int>> To(H,vector<int>(W));
for(int i=0; i<H; i++){
auto [siz,p] = D1.at(i);
if(siz == 1) continue;
for(int k=0; k<W; k++) if(S.at(i).at(k) != '#'){
int pos = i*W+k;
To.at(i).at(k) = k;
if(k && S.at(i).at(k-1) != '#') To.at(i).at(k) = To.at(i).at(k-1);
int l = To.at(i).at(k),r = k;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = i*W+l-siz;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = i*W+r-siz;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
for(int k=W; k--;) if(S.at(i).at(k) != '#'){
int pos = i*W+k;
To.at(i).at(k) = k;
if(k < W-1 && S.at(i).at(k+1) != '#') To.at(i).at(k) = To.at(i).at(k+1);
int l = k+1,r = To.at(i).at(k)+1;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = i*W+l-siz;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = i*W+r-siz;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
}
}
{
vector<pair<int,int>> D2(W);
for(int k=0; k<W; k++){
int s = H,siz = 1;
while(siz < s) siz += siz;
D2.at(k) = {siz,n};
if(siz == 1) continue;
for(int i=0; i<siz+siz; i++) Graph.push_back({});
for(int i=1; i<siz; i++){
if(i+i >= siz){
int left = i+i-siz,right = left+1;
if(left < H) Graph.at(n+i).push_back({left*W+k,0});
if(right < W) Graph.at(n+i).push_back({right*W+k,0});
}
else{
int left = i+i,right = i+i+1;
Graph.at(n+i).push_back({n+left,0});
Graph.at(n+i).push_back({n+right,0});
}
}
n += siz;
for(int i=1; i<siz; i++){
if(i+i >= siz){
int left = i+i-siz,right = left+1;
if(left < H) Graph.at(n+i).push_back({left*W+k+N,0});
if(right < W) Graph.at(n+i).push_back({right*W+k+N,0});
}
else{
int left = i+i,right = i+i+1;
Graph.at(n+i).push_back({n+left,0});
Graph.at(n+i).push_back({n+right,0});
}
}
n += siz;
}
vector<vector<int>> To(H,vector<int>(W));
for(int k=0; k<W; k++){
auto [siz,p] = D2.at(k);
if(siz == 1) continue;
for(int i=0; i<H; i++) if(S.at(i).at(k) != '#'){
int pos = i*W+k;
To.at(i).at(k) = i;
if(i && S.at(i-1).at(k) != '#') To.at(i).at(k) = To.at(i-1).at(k);
int l = To.at(i).at(k),r = i;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = (l-siz)*W+k;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = (r-siz)*W+k;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
for(int i=H; i--;) if(S.at(i).at(k) != '#'){
int pos = i*W+k;
To.at(i).at(k) = i;
if(i < H-1 && S.at(i+1).at(k) != '#') To.at(i).at(k) = To.at(i+1).at(k);
int l = i+1,r = To.at(i).at(k)+1;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = (l-siz)*W+k;
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = (r-siz)*W+k;
Graph.at(pos).push_back({N+to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
}
}
{
vector<pair<int,int>> D3(H+W);
for(int p=0; p<H+W-1; p++){
int x = 0,y = 0;
if(p < H) x = p;
else y = p-H+1;
int s = min(H-x,W-y),siz = 1;
while(siz < s) siz += siz;
D3.at(p) = {siz,n};
if(siz == 1) continue;
for(int k=0; k<siz+siz; k++) Graph.push_back({});
for(int k=1; k<siz; k++){
if(k+k >= siz){
int left = k+k-siz,right = k+k-siz+1;
if(x+left < H && y+left < W) Graph.at(n+k).push_back({(x+left)*W+(y+left),0});
if(x+right < H && y+right < W) Graph.at(n+k).push_back({(x+right)*W+(y+right),0});
}
else{
int left = k+k,right = k+k+1;
Graph.at(n+k).push_back({n+left,0});
Graph.at(n+k).push_back({n+right,0});
}
}
n += siz;
for(int k=1; k<siz; k++){
if(k+k >= siz){
int left = k+k-siz,right = k+k-siz+1;
if(x+left < H && y+left < W) Graph.at(n+k).push_back({(x+left)*W+(y+left)+N,0});
if(x+right < H && y+right < W) Graph.at(n+k).push_back({(x+right)*W+(y+right)+N,0});
}
else{
int left = k+k,right = k+k+1;
Graph.at(n+k).push_back({n+left,0});
Graph.at(n+k).push_back({n+right,0});
}
}
n += siz;
}
vector<vector<int>> To(H,vector<int>(W));
for(int i=0; i<H; i++){
for(int k=0; k<W; k++) if(S.at(i).at(k) != '#'){
int siz,p;
if(i >= k) tie(siz,p) = D3.at(i-k);
else tie(siz,p) = D3.at(k-i+H-1);
if(siz == 1) continue;
int pos = i*W+k;
To.at(i).at(k) = k;
if(i && k && S.at(i-1).at(k-1) != '#') To.at(i).at(k) = To.at(i-1).at(k-1);
int lx = To.at(i).at(k)-(k-i),ly = To.at(i).at(k);
int Lx = lx-min(lx,ly),Ly = ly-min(lx,ly);
int l = min(lx,ly),r = min(i,k);
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = (Lx+l-siz)*W+(Ly+l-siz);
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = (Lx+r-siz)*W+(Ly+r-siz);
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
}
for(int i=H-1; i>=0; i--){
for(int k=0; k<W; k++) if(S.at(i).at(k) != '#'){
int siz,p;
if(i >= k) tie(siz,p) = D3.at(i-k);
else tie(siz,p) = D3.at(k-i+H-1);
if(siz == 1) continue;
int pos = i*W+k;
To.at(i).at(k) = k;
if(i < H-1 && k < W-1 && S.at(i+1).at(k+1) != '#') To.at(i).at(k) = To.at(i+1).at(k+1);
int rx = To.at(i).at(k)-(k-i),ry = To.at(i).at(k);
int Lx = rx-min(rx,ry),Ly = ry-min(rx,ry);
int l = min(i,k)+1,r = min(rx,ry)+1;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = (Lx+l-siz)*W+(Ly+l-siz);
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = (Lx+r-siz)*W+(Ly+r-siz);
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
}
}
{
vector<pair<int,int>> D4(H+W);
for(int p=0; p<H+W-1; p++){
int x = 0,y = 0;
if(p < W) y = p;
else x = p-W+1,y = W-1;
int s = min(H-x,y+1),siz = 1;
while(siz < s) siz += siz;
D4.at(p) = {siz,n};
if(siz == 1) continue;
for(int k=0; k<siz+siz; k++) Graph.push_back({});
for(int k=1; k<siz; k++){
if(k+k >= siz){
int left = k+k-siz,right = k+k-siz+1;
if(x+left < H && y-left >= 0) Graph.at(n+k).push_back({(x+left)*W+(y-left),0});
if(x+right < H && y-right >= 0) Graph.at(n+k).push_back({(x+right)*W+(y-right),0});
}
else{
int left = k+k,right = k+k+1;
Graph.at(n+k).push_back({n+left,0});
Graph.at(n+k).push_back({n+right,0});
}
}
n += siz;
for(int k=1; k<siz; k++){
if(k+k >= siz){
int left = k+k-siz,right = k+k-siz+1;
if(x+left < H && y-left >= 0) Graph.at(n+k).push_back({(x+left)*W+(y-left)+N,0});
if(x+right < H && y-right >= 0) Graph.at(n+k).push_back({(x+right)*W+(y-right)+N,0});
}
else{
int left = k+k,right = k+k+1;
Graph.at(n+k).push_back({n+left,0});
Graph.at(n+k).push_back({n+right,0});
}
}
n += siz;
}
vector<vector<int>> To(H,vector<int>(W));
for(int i=0; i<H; i++){
for(int k=0; k<W; k++) if(S.at(i).at(k) != '#'){
auto [siz,p] = D4.at(i+k);
if(siz == 1) continue;
int pos = i*W+k;
To.at(i).at(k) = k;
if(i && k < W-1 && S.at(i-1).at(k+1) != '#') To.at(i).at(k) = To.at(i-1).at(k+1);
int lx = i+k-To.at(i).at(k),ly = To.at(i).at(k);
int Lx = 0,Ly = i+k;
if(Ly >= W) Lx += Ly-W+1,Ly = W-1;
int l = lx-Lx,r = i-Lx;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = (Lx+l-siz)*W+(Ly-(l-siz));
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = (Lx+r-siz)*W+(Ly-(r-siz));
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
}
for(int i=H-1; i>=0; i--){
for(int k=0; k<W; k++) if(S.at(i).at(k) != '#'){
auto [siz,p] = D4.at(i+k);
if(siz == 1) continue;
int pos = i*W+k;
To.at(i).at(k) = k;
if(i < H-1 && k && S.at(i+1).at(k-1) != '#') To.at(i).at(k) = To.at(i+1).at(k-1);
int rx = i+k-To.at(i).at(k),ry = To.at(i).at(k);
int Lx = 0,Ly = i+k;
if(Ly >= W) Lx += Ly-W+1,Ly = W-1;
int l = i-Lx+1,r = rx-Lx+1;
l += siz,r += siz;
while(l < r){
if(l&1){
if(l >= siz){
int to = (Lx+l-siz)*W+(Ly-(l-siz));
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1});
l++;
}
if(r&1){
r--;
if(r >= siz){
int to = (Lx+r-siz)*W+(Ly-(r-siz));
Graph.at(pos).push_back({N+to,1});
Graph.at(N+pos).push_back({to,1});
}
else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1});
}
l >>= 1,r >>= 1;
}
}
}
}
int ok = 0;
vector<int> dist(n,1001001001);
dist.at(sx*W+sy) = 0;
deque<int> Q; Q.push_back({sx*W+sy});
while(Q.size()){
auto pos = Q.front(); Q.pop_front();
ok++;
int d = dist.at(pos);
for(auto [to,w] : Graph.at(pos)){
int v = d+w;
if(w == 1){
if(dist.at(to) > v) dist.at(to) = v,Q.push_back(to);
}
else if(dist.at(to) > v) dist.at(to) = v,Q.push_front(to);
}
}
int q; cin >> q;
if(ok == 1){
while(q--) cout << "No\n";
return 0;
}
while(q--){
int gx,gy,t; cin >> gx >> gy >> t,gx--,gy--;
int pos = gx*W+gy;
if(t%2) pos += N;
int now = dist.at(pos);
if(now == 1001001001) continue;
assert(now%2 == t%2);
if(now <= t) cout << "Yes\n";
else cout << "No\n";
}
return 0;
for(int i=0; i<H; i++,cout<<"\n") for(int k=0; k<W; k++) cout << dist.at(i*W+k) << " ";
cout << endl;
for(int i=0; i<H; i++,cout<<"\n") for(int k=0; k<W; k++) cout << dist.at(i*W+k+N) << " ";
}