Submission #539162

#	Time	Username	Problem	Language	Result	Execution time	Memory
539162		astoria	물병 (JOI14_bottle)	C++14	100 / 100	2254 ms	144740 KiB

bottle

#include <bits/stdc++.h>
using namespace std;

int h,w,p,qq;
char mp[2005][2005];
int ufds_par[200005];
unordered_set<int> qr_at[200005];
int ans[200005];
int xc[200005], yc[200005];

int colour[2005][2005];
int dist[2005][2005];

int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};

int root(int x){
    if(ufds_par[x] == -1) return x;
    return ufds_par[x] = root(ufds_par[x]);
}

void merge(int x, int y, int d){
    for(int i : qr_at[y]){
        if(qr_at[x].count(i)){
            ans[i] = d;
            qr_at[x].erase(i);
        }
        else qr_at[x].insert(i);
    }
    qr_at[y].clear();
}

void connect(int u, int v, int d){
    int x=root(u), y=root(v);
    if(x==y) return;
    if(qr_at[x].size() > qr_at[y].size()){
        merge(x,y,d);
        ufds_par[y] = x;
    }
    else{ merge(y,x,d); ufds_par[x] = y;}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>h>>w>>p>>qq;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            cin>>mp[i][j];
        }
    }
    for(int i=1; i<=p; i++) cin>>xc[i]>>yc[i];
    for(int i=0; i<qq; i++){
        int a,b;
        cin>>a>>b;
        qr_at[a].insert(i); qr_at[b].insert(i);
    }//input
    
    memset(ufds_par,-1,sizeof(ufds_par));
    
    //Multi-BFS
    queue<pair<int,int> > q;
    memset(dist,-1,sizeof(dist));
    memset(colour,-1,sizeof(colour));
    memset(ans,-1,sizeof(ans));
    for(int i=1; i<=p; i++){
        dist[xc[i]][yc[i]] = 0;
        colour[xc[i]][yc[i]] = i;
        q.emplace(xc[i],yc[i]);
    }
    int ld = 0;
    vector<pair<int,pair<int,int> > > edg;
    while(!q.empty()){
        int x=q.front().first, y=q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<=0||nx>h||ny<=0||ny>w) continue;
            if(mp[nx][ny] == '#') continue;
            if(dist[nx][ny]==-1){
                dist[nx][ny] = dist[x][y]+1;
                colour[nx][ny] = colour[x][y];
                q.push(make_pair(nx,ny));
            }
            else{
            	//All offline.
            	if(colour[x][y] == colour[nx][ny]) continue;
				edg.push_back(make_pair(dist[x][y]+dist[nx][ny],make_pair(colour[x][y],colour[nx][ny])));
            }
        }
    }
    sort(edg.begin(),edg.end());
	for(auto i : edg){
		int w=i.first, u=i.second.first, v=i.second.second;
		if(root(u)==root(v)) continue;
		connect(u,v,w);
	}
    
    for(int i=0; i<qq; i++){
    	//assert(ans[i]!=-1);
        cout<<ans[i]<<'\n';
    }
    /*for(int i=1; i<=p; i++){
    	cout<<root(i);
    }*/
}

Compilation message (stderr)

bottle.cpp: In function 'int main()':
bottle.cpp:71:9: warning: unused variable 'ld' [-Wunused-variable]
   71 |     int ld = 0;
      |         ^~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30