結果
問題 | No.2786 RMQ on Grid Path |
ユーザー |
|
提出日時 | 2024-06-14 22:32:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5,141 ms / 6,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 5,765 ms |
コンパイル使用メモリ | 317,996 KB |
実行使用メモリ | 72,832 KB |
最終ジャッジ日時 | 2024-06-14 22:34:27 |
合計ジャッジ時間 | 91,600 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace atcoder; using namespace std; int main(){ int h,w; cin>>h>>w; int m=h*w; vector<int> a(m); vector<vector<int>> b(m+1); vector<vector<int>> next(m); vector<int> dx={1,0,-1,0},dy={0,1,0,-1}; for(int i=0;i<h;i++)for(int j=0;j<w;j++){ for(int k=0;k<4;k++){ int nx=i+dx[k],ny=j+dy[k]; if(nx<0||nx>=h||ny<0||ny>=w)continue; next[i*w+j].push_back(nx*w+ny); } } for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>a[i*w+j]; for(int i=0;i<m;i++){ b[a[i]].push_back(i); } int q; cin>>q; vector<vector<int>> lr(q); for(int i=0;i<q;i++)lr[i]={0,m}; vector<vector<int>> qs(q,vector<int>(4)); for(int i=0;i<q;i++){ for(int j=0;j<4;j++){ cin>>qs[i][j]; qs[i][j]--; } } while(1){ bool end=true; for(int i=0;i<q;i++)if(lr[i][1]-lr[i][0]!=1)end=false; if(end)break; vector<set<int>> s(m+1); for(int i=0;i<q;i++){ s[(lr[i][1]+lr[i][0])/2].insert(i); } dsu uf(m); vector<bool> state(m,false); for(int i=0;i<=m;i++){ for(int x:b[i]){ state[x]=true; for(int y:next[x]){ if(state[y])uf.merge(x,y); } } for(int x:s[i]){ if(uf.same(qs[x][0]*w+qs[x][1],qs[x][2]*w+qs[x][3]))lr[x][1]=i; else lr[x][0]=i; } } } for(int i=0;i<q;i++)cout<<lr[i][1]<<endl; }