Submission #1193101

#TimeUsernameProblemLanguageResultExecution timeMemory
1193101vnedu물병 (JOI14_bottle)C++17
30 / 100
321 ms46576 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); } template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); } #define fi first #define se second #define pb push_back #define ii pair<int, int> #define all(x) x.begin(), x.end() #define TASK "nonsense" /// end of template /// const int N = 2e3 + 10; const int P = 2e5 + 10; const int Q = 2e5 + 10; const int M = 2e5 + 10; const int inf = 1e9; struct Dsu { int n,par[M]; Dsu() {} void init(int _n) { n=_n; for(int i=1;i<=n;++i) par[i]=i; } int get(int x) { if(x==par[x]) return x; return par[x]=get(par[x]); } bool unite(int x, int y) { int s=get(x),t=get(y); if(s==t) return 0; par[s]=t; return 1; } } dsu; struct Edge { int u,v,w; Edge() {} Edge(int u, int v, int w) : u(u),v(v),w(w) {} } edge[P]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int n,m,_p,numQuery,numEdge=0,lo[Q],hi[Q],mid[Q],ans[Q],cur[Q],ptr; char a[N][N]; ii p[P],dp[N][N],query[Q]; queue<ii> q; bool ok[Q],process[N][N]; bool cmp(int x, int y) { return mid[x]<mid[y]; } void solve() { cin>>n>>m>>_p>>numQuery; for(int i=1;i<=n;++i) { string s; cin>>s; for(int j=1;j<=m;++j) a[i][j]=s[j-1]; } for(int i=1;i<=_p;++i) { int x,y; cin>>x>>y; dp[x][y]=make_pair(i,0); q.push(make_pair(x,y)); } dsu.init(_p); while(!q.empty()) { int i=q.front().fi; int j=q.front().se; process[i][j]=1; // cout<<i<<' '<<j<<" "<<dp[i][j].fi<<' '<<dp[i][j].se<<'\n'; q.pop(); for(int k=0;k<4;++k) { int i2=i+dx[k]; int j2=j+dy[k]; if(i2>=1 && i2<=n && j2>=1 && j2<=m && a[i2][j2]!='#') { if(dp[i2][j2].fi==0) { dp[i2][j2]={dp[i][j].fi,dp[i][j].se+1}; q.push({i2,j2}); } else if(process[i2][j2] && dsu.get(dp[i][j].fi)!=dsu.get(dp[i2][j2].fi)) { int u=dp[i][j].fi,v=dp[i2][j2].fi; // cout<<"XXX "<<u<<' '<<v<<" XXX\n"; edge[++numEdge]=Edge(u,v,dp[i][j].se+dp[i2][j2].se); dsu.unite(u,v); } } } } // for(int i=1;i<=numEdge;++i) // { // cout<<edge[i].u<<' '<<edge[i].v<<' '<<edge[i].w<<'\n'; // } // return; for(int i=1;i<=numQuery;++i) { cin>>query[i].fi>>query[i].se; ans[i]=inf; lo[i]=1; hi[i]=numEdge; } for(int tri=1;tri<=20;++tri) { ptr=0; memset(ok,0,sizeof(ok)); dsu.init(_p); for(int i=1;i<=numQuery;++i) if(lo[i]<=hi[i]) { mid[i]=(lo[i]+hi[i])>>1; cur[++ptr]=i; } // break; sort(cur+1,cur+1+ptr,cmp); int num=0; for(int i=1;i<=ptr;++i) { int id=cur[i]; while(num<mid[id]) { ++num; dsu.unite(edge[num].u,edge[num].v); } ok[id]=(dsu.get(query[id].fi)==dsu.get(query[id].se)); } // break; for(int i=1;i<=numQuery;++i) if(lo[i]<=hi[i]) { if(ok[i]) ans[i]=edge[mid[i]].w,hi[i]=mid[i]-1; else lo[i]=mid[i]+1; } } for(int i=1;i<=numQuery;++i) cout<<(ans[i]==inf?-1:ans[i])<<'\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); int testcase=1; // cin>>testcase; while (testcase--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...