oj.uz

Submission #910985

# Submission time Handle Problem Language Result Execution time Memory
910985 2024-01-18T10:38:42 Z dsyz 물병 (JOI14_bottle) C++17
100 / 100
 1228 ms 127780 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57948 KB Output is correct
2 Correct 12 ms 59996 KB Output is correct
3 Correct 14 ms 59996 KB Output is correct
4 Correct 61 ms 62036 KB Output is correct
5 Correct 61 ms 62084 KB Output is correct
6 Correct 61 ms 61972 KB Output is correct
7 Correct 60 ms 62032 KB Output is correct
8 Correct 62 ms 62232 KB Output is correct
9 Correct 64 ms 62204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 74876 KB Output is correct
2 Correct 40 ms 61372 KB Output is correct
3 Correct 306 ms 79020 KB Output is correct
4 Correct 417 ms 81980 KB Output is correct
5 Correct 475 ms 84340 KB Output is correct
6 Correct 290 ms 79228 KB Output is correct
7 Correct 457 ms 81668 KB Output is correct
8 Correct 471 ms 84640 KB Output is correct
9 Correct 480 ms 89964 KB Output is correct
10 Correct 314 ms 79348 KB Output is correct
11 Correct 360 ms 80472 KB Output is correct
12 Correct 137 ms 81700 KB Output is correct
13 Correct 121 ms 78856 KB Output is correct
14 Correct 115 ms 81252 KB Output is correct
15 Correct 119 ms 78940 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 74888 KB Output is correct
2 Correct 32 ms 60800 KB Output is correct
3 Correct 180 ms 78244 KB Output is correct
4 Correct 450 ms 81716 KB Output is correct
5 Correct 470 ms 84608 KB Output is correct
6 Correct 468 ms 88480 KB Output is correct
7 Correct 264 ms 79308 KB Output is correct
8 Correct 412 ms 81720 KB Output is correct
9 Correct 144 ms 81464 KB Output is correct
10 Correct 129 ms 79092 KB Output is correct
11 Correct 116 ms 78636 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 82140 KB Output is correct
2 Correct 836 ms 99820 KB Output is correct
3 Correct 244 ms 79368 KB Output is correct
4 Correct 986 ms 108296 KB Output is correct
5 Correct 1228 ms 119448 KB Output is correct
6 Correct 513 ms 87808 KB Output is correct
7 Correct 361 ms 79412 KB Output is correct
8 Correct 90 ms 79068 KB Output is correct
9 Correct 985 ms 127780 KB Output is correct
10 Correct 724 ms 100640 KB Output is correct
11 Correct 1014 ms 119492 KB Output is correct
12 Correct 782 ms 109544 KB Output is correct