| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15895 |
2015-08-01T06:55:25 Z |
comet |
물병 (JOI14_bottle) |
C++ |
|
692 ms |
75808 KB |
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define INF (1e9)
struct edge{
int v,u,c;
bool operator<(const edge& r)const{
return c<r.c;
}
};
struct pt{
int y,x;
pt(int y_=0,int x_=0):
y(y_),x(x_){}
};
struct disjoint{
vector<int> p;
disjoint(int n):p(n+1){
for(int i=1;i<=n;i++)p[i]=i;
}
int find(int x){
if(p[x]==x)return x;
return p[x]=find(p[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return 0;
p[x]=y;
return 1;
}
};
int H,W,P;
int dist[2010][2010],area[2010][2010];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int par[200010][20],RMQ[200010][20],in[200010],out[200010],T;
vector<pt> path[200010];
queue<pt> Q;
char a[2010][2010];
void kruskal(vector<edge>& s){
int n=s.size(),i;
edge e;
disjoint alice(P);
for(i=0;i<n;i++){
e=s[i];
if(alice.merge(e.v,e.u)){
path[e.v].push_back(pt(e.u,e.c));
path[e.u].push_back(pt(e.v,e.c));
}
}
for(int i=1;i<P;i++){
if(alice.merge(i,i+1)){
path[i].push_back(pt(i+1,INF));
path[i+1].push_back(pt(i,INF));
}
}
}
void dfs(int v,int p,int c){
pt u;
par[v][0]=p;
RMQ[v][0]=c;
in[v]=T++;
for(int i=1;i<20;i++){
par[v][i]=par[par[v][i-1]][i-1];
RMQ[v][i]=max(RMQ[par[v][i-1]][i-1],RMQ[v][i-1]);
}
for(int i=0;i<path[v].size();i++){
u=path[v][i];
if(u.y==p)continue;
dfs(u.y,v,u.x);
}
out[v]=T++;
}
void init(){
pt v,u;
while(!Q.empty()){
v=Q.front();
Q.pop();
for(int i=0;i<4;i++){
u=pt(v.y+dy[i],v.x+dx[i]);
if(u.y<=0||u.x<=0||u.y>H||u.x>W)continue;
if(a[u.y][u.x]=='#')continue;
if(area[u.y][u.x])continue;
area[u.y][u.x]=area[v.y][v.x];
dist[u.y][u.x]=dist[v.y][v.x]+1;
Q.push(u);
}
}
vector<edge> s;
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
if(i<H&&area[i][j]!=area[i+1][j]&&area[i][j]&&area[i+1][j])
s.push_back(edge{area[i][j],area[i+1][j],dist[i][j]+dist[i+1][j]});
if(j<W&&area[i][j]!=area[i][j+1]&&area[i][j]&&area[i][j+1])
s.push_back(edge{area[i][j],area[i][j+1],dist[i][j]+dist[i][j+1]});
}
}
kruskal(s);
dfs(1,1,0);
}
bool isParent(int x,int y){
return in[x]<=in[y]&&out[x]>=out[y];
}
int LCA(int x,int y){
if(isParent(x,y))return x;
if(isParent(y,x))return y;
for(int i=19;i>=0;i--){
if(!isParent(par[x][i],y))
x=par[x][i];
}
return par[x][0];
}
int f(int p,int v){
if(p==v)return 0;
int ret=0;
for(int i=19;i>=0;i--){
if(isParent(p,par[v][i])){
ret=max(ret,RMQ[v][i]);
v=par[v][i];
}
}
//if(v!=p)cout<<"wowowowowo wonderful!!!"<<endl;
return ret;
}
int query(int x,int y){
int t=LCA(x,y);
return max(f(t,x),f(t,y));
}
int main(){
ios::sync_with_stdio(0);
int m,x,y,ans;
cin>>H>>W>>P>>m;
for(int i=1;i<=H;i++)cin>>&a[i][1];
for(int i=1;i<=P;i++){
cin>>y>>x;
area[y][x]=i;
Q.push(pt(y,x));
}
init();
while(m--){
cin>>x>>y;
ans=query(x,y);
if(ans>=INF)cout<<"-1"<<endl;
else cout<<ans<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
74860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
75260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
75260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
692 ms |
75808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
