Submission #910985

#	Time	Username	Problem	Language	Result	Execution time	Memory
910985		dsyz	물병 (JOI14_bottle)	C++17	100 / 100	1228 ms	127780 KiB

bottle

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (200005)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
ll H,W,P,Q;
char arr[2005][2005];
ll DIST[2005][2005], visited[2005][2005];
pair<ll,ll> building[MAXN];
ll par[MAXN];
ll find_set(ll x){
  	if(par[x] == x) return x;
  	par[x] = find_set(par[x]);
  	return par[x];
}
bool same_set(ll x,ll y){
	return find_set(x) == find_set(y);
}
void merge_set(ll x,ll y){
	if(same_set(x,y)) return;
	par[find_set(x)] = find_set(y);
}
vector<pair<ll,ll> > v[MAXN];
ll dist[MAXN], depth[MAXN];
ll parent[19][MAXN], maxonlev[19][MAXN];
bool vis[MAXN];
void dfs(ll x,ll nodeparent,ll nodedepth){
	vis[x] = 1;
  	parent[0][x] = nodeparent;
  	depth[x] = nodedepth;
  	for(ll i = 0;i < v[x].size();i++){
    	if(v[x][i].first != nodeparent){
      		maxonlev[0][v[x][i].first] = v[x][i].second;
      		dfs(v[x][i].first,x,nodedepth + 1);
    	}
  	}
}
void lcainit(){
  	for(ll i = 1;i < 19;i++){
    	for(ll j = 0;j < P;j++){
      		parent[i][j] = parent[i - 1][parent[i - 1][j]];
      		maxonlev[i][j] = max(maxonlev[i - 1][j],maxonlev[i - 1][parent[i - 1][j]]);
    	}
  	}
}
ll lca(ll u,ll v){
  	ll ans = 0;
  	if(depth[u] > depth[v]){
    	swap(u,v);
  	}
  	ll diff = depth[v] - depth[u];
  	for(ll i = 0;i < 19;i++){
    	if(diff & (1<<i)){
      		ans = max(ans,maxonlev[i][v]);
      		v = parent[i][v];
    	}
  	}
 	if(u == v){
    	return ans;
  	}
  	for(ll i = 18;i >= 0;i--){
    	if(parent[i][u] != parent[i][v]){
      		ans = max(ans,maxonlev[i][u]);
      		ans = max(ans,maxonlev[i][v]);
      		u = parent[i][u];
      		v = parent[i][v];
    	}
  	}
  	ans = max(ans,maxonlev[0][u]);
  	ans = max(ans,maxonlev[0][v]);
  	return ans;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>H>>W>>P>>Q;
	for(ll i = 0;i < H;i++){
		for(ll j = 0;j < W;j++){
			cin>>arr[i][j];
		}
	}
	queue<pair<pair<ll,ll>,ll> > q; //x, y, source
	memset(visited,-1,sizeof(visited));
	for(ll i = 0;i < P;i++){
		cin>>building[i].first>>building[i].second;
		building[i].first--;
		building[i].second--;
		q.push({{building[i].first,building[i].second},i});
		DIST[building[i].first][building[i].second] = 0;
		visited[building[i].first][building[i].second] = i;
	}
	int Hy[] = {0,0,-1,1};
	int Wx[] = {-1,1,0,0};
	while(!q.empty()){
		ll y = q.front().first.first;
		ll x = q.front().first.second;
		ll source = q.front().second;
		q.pop();
		visited[y][x] = source;
		for(ll i = 0;i < 4;i++){
			ll a = y + Hy[i];
			ll b = x + Wx[i];
			if(a < 0 || a >= H || b < 0 || b >= W || arr[a][b] == '#' || visited[a][b] != -1){
				continue;
			}
			q.push({{a,b},source});
			DIST[a][b] = DIST[y][x] + 1;
			visited[a][b] = source;
		}
	}
	for(ll i = 0;i < P;i++){
		par[i] = i;
	}
	vector<pair<ll,pair<ll,ll> > > edges;
	for(ll y = 0;y < H;y++){
		for(ll x = 0;x < W;x++){
			if(arr[y][x] == '#' || visited[y][x] == -1) continue;
			for(ll i = 0;i < 4;i++){
				ll a = y + Hy[i];
				ll b = x + Wx[i];
				if(a < 0 || a >= H || b < 0 || b >= W || arr[a][b] == '#' || visited[a][b] == -1){
					continue;
				}
				if(visited[y][x] != visited[a][b]){
					edges.push_back({DIST[y][x] + DIST[a][b],{visited[y][x],visited[a][b]}});
				}
			}
		}
	}
	sort(edges.begin(),edges.end());
	for(auto u : edges){
		ll a = u.second.first;
		ll b = u.second.second;
		ll c = u.first;
		if(same_set(a,b)) continue;
		merge_set(a,b);
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	for(ll x = 0;x < P;x++){
		if(!vis[x]){
			dfs(x,0,0);
		}
	}
	lcainit();
	for(ll q = 0;q < Q;q++){
		ll a,b;
		cin>>a>>b;
		a--, b--;
		if(!same_set(a,b)){
			cout<<-1<<'\n';
		}else{
			cout<<lca(a,b)<<'\n';
		}
	}
}

Compilation message (stderr)

bottle.cpp: In function 'void dfs(ll, ll, ll)':
bottle.cpp:32:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(ll i = 0;i < v[x].size();i++){
      |                 ~~^~~~~~~~~~~~~

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