Submission #43353

#TimeUsernameProblemLanguageResultExecution timeMemory
43353ffresh물병 (JOI14_bottle)C++14
0 / 100
394 ms34672 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2005,M = 2e5+15,T = 20; int color[N][N]; int py[M],px[M]; vector<pair<int,int> >adj[N]; int par[M]; int f(int x){ if(x==par[x])return x; return par[x]= f(par[x]); } bool vis[M]; int dy[4]= {1,-1,0,0},dx[4]= {0,0,1,-1}; int dist(int id,int y,int x){ return abs(py[id]-y)+ abs(px[id]-x); } int depth[M],lca[M][T],value[M][T]; void dfs(int root,int p){ depth[root]= depth[p]+1; vis[root]= 1; for(int i=1;i<T;++i){ lca[root][i]= lca[lca[root][i-1]][i-1]; value[root][i]= max(value[root][i-1], value[lca[root][i-1]][i-1]); } for(int i=0;i<adj[root].size();++i){ int u = adj[root][i].second; int m = adj[root][i].first; if(u==p)continue; lca[u][0]= root; value[u][0]= m; dfs(u,root); } } int getvalue(int x,int y){ if(depth[x]<depth[y])swap(x,y); int D= depth[x]-depth[y]; int val = 0; for(int i=0;i<T;++i){ if(D&(1<<i)){ val= max(val, value[x][i]); x = lca[x][i]; } } if(x!=y){ for(int i=T-1;i>=0;--i){ if(lca[x][i]!= lca[y][i]){ val = max(val,value[x][i]); val = max(val,value[y][i]); x = lca[x][i],y = lca[y][i]; } } val = max(val,max(value[x][0],value[y][0])); } return val; } int main(){ //freopen("input.txt","r",stdin); int h,w,p,q; cin>>h>>w>>p>>q; for(int i=1;i<=h;++i){ string s;cin>>s; for(int j=1;j<=w;++j){ if(s[j-1]=='#'){ color[i][j]= -1; } } } int y,x; queue<pair<pair<int,int>,int> >qq,temp; for(int i=1;i<=p;++i) { par[i]= i; scanf("%d%d",&py[i],&px[i]); color[py[i]][px[i]]= i; qq.push(make_pair(make_pair(py[i],px[i]),i )); } while(!qq.empty()){ while(!qq.empty()){ int id= qq.front().second, y = qq.front().first.first, x = qq.front().first.second; qq.pop(); for(int j=0;j<4;++j){ int ny = dy[j]+ y, nx = dx[j] + x; if(ny>0 && ny<=h && nx>0 && nx<=w && color[ny][nx]==0){ color[ny][nx]= id; temp.push(make_pair(make_pair(ny,nx),id)); } } } swap(qq,temp); } vector<pair<int,pair<int,int> > >Edge; for(int i=1;i<h;++i){ for(int j=1;j<w;++j){ if(color[i][j]!=-1){ int id = color[i][j]; int id2= color[i][j+1]; if(id2!=id && id2!=-1){ Edge.push_back(make_pair(dist(id,i,j)+ dist(id2,i,j+1),make_pair(id,id2))); } id2 = color[i+1][j]; if(id2!=id && id2!=-1){ Edge.push_back(make_pair(dist(id,i,j)+ dist(id2,i+1,j),make_pair(id,id2))); } } } } sort(Edge.begin(),Edge.end()); for(int i=0;i<(int)Edge.size();++i){ int a = Edge[i].second.first, b = Edge[i].second.second; if(f(a)!=f(b)){ par[f(b)]= f(a); //cout<<a<<" "<<b<<" "<<Edge[i].first<<endl; adj[a].push_back(make_pair(Edge[i].first,b)); adj[b].push_back(make_pair(Edge[i].first,a)); } } for(int i=1;i<=p;++i){ if(!vis[i]){ dfs(i,0); } } while(q--){ scanf("%d%d",&x,&y); if(f(x)!=f(y)){ printf("-1\n"); } else{ printf("%d\n",getvalue(x,y)); } } }

Compilation message (stderr)

bottle.cpp: In function 'void dfs(int, int)':
bottle.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[root].size();++i){
               ^
bottle.cpp: In function 'int main()':
bottle.cpp:100:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&py[i],&px[i]);
                              ^
bottle.cpp:169:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...