oj.uz

Submission #539162

# Submission time Handle Problem Language Result Execution time Memory
539162 2022-03-18T14:05:08 Z astoria 물병 (JOI14_bottle) C++14
100 / 100
 2254 ms 144740 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 44756 KB Output is correct
2 Correct 29 ms 45000 KB Output is correct
3 Correct 26 ms 45012 KB Output is correct
4 Correct 697 ms 71992 KB Output is correct
5 Correct 720 ms 73220 KB Output is correct
6 Correct 779 ms 71956 KB Output is correct
7 Correct 640 ms 70268 KB Output is correct
8 Correct 792 ms 73644 KB Output is correct
9 Correct 716 ms 73188 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 48936 KB Output is correct
2 Correct 62 ms 47068 KB Output is correct
3 Correct 392 ms 53416 KB Output is correct
4 Correct 583 ms 56048 KB Output is correct
5 Correct 580 ms 59436 KB Output is correct
6 Correct 329 ms 53412 KB Output is correct
7 Correct 467 ms 55996 KB Output is correct
8 Correct 522 ms 59540 KB Output is correct
9 Correct 581 ms 65972 KB Output is correct
10 Correct 425 ms 54068 KB Output is correct
11 Correct 464 ms 55764 KB Output is correct
12 Correct 157 ms 55696 KB Output is correct
13 Correct 294 ms 53248 KB Output is correct
14 Correct 151 ms 55684 KB Output is correct
15 Correct 234 ms 53260 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49208 KB Output is correct
2 Correct 60 ms 45912 KB Output is correct
3 Correct 292 ms 53516 KB Output is correct
4 Correct 523 ms 57288 KB Output is correct
5 Correct 613 ms 60696 KB Output is correct
6 Correct 649 ms 67208 KB Output is correct
7 Correct 472 ms 55008 KB Output is correct
8 Correct 528 ms 57292 KB Output is correct
9 Correct 193 ms 57004 KB Output is correct
10 Correct 269 ms 54896 KB Output is correct
11 Correct 227 ms 53620 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1355 ms 85104 KB Output is correct
2 Correct 1773 ms 113356 KB Output is correct
3 Correct 452 ms 54288 KB Output is correct
4 Correct 1998 ms 121296 KB Output is correct
5 Correct 2240 ms 144740 KB Output is correct
6 Correct 1579 ms 93536 KB Output is correct
7 Correct 419 ms 54228 KB Output is correct
8 Correct 126 ms 53420 KB Output is correct
9 Correct 2160 ms 144540 KB Output is correct
10 Correct 2021 ms 122328 KB Output is correct
11 Correct 2254 ms 144048 KB Output is correct
12 Correct 2055 ms 130008 KB Output is correct