Submission #676460

#	Time	Username	Problem	Language	Result	Execution time	Memory
676460		penguin133	물병 (JOI14_bottle)	C++17	100 / 100	1222 ms	195700 KiB

bottle

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n, q, r, c;
priority_queue<pair<pi, pii> , vector<pair<pi, pii> >, greater<pair<pi, pii> > > pq;
int A[2005][2005], dist[2005][2005];
char G[2005][2005];
int par[20][200005], mx[20][200005];
vector<int>v[200005];
vector<pi>adj[200005];
int dep[200005];
int root[200005];
pi haha[200005];
vector<pii>edges;
map<pair<int, int> , int> m;
int getr(int x){
	return (root[x] == x ? x : root[x] = getr(root[x]));
}
void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a != b)root[b] = a;
}
void dfs(int x, int p, int d){
	par[0][x] = p;
	dep[x] = d;
	for(auto [i, j] : adj[x]){
		if(i != p)dfs(i, x, d+1);
		else mx[0][x] = j;
	}
}
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int diff = dep[v] - dep[u];
	int ans = 0;
	for(int i=0;i<19;i++)if(diff >> i & 1)ans = max(ans, mx[i][v]), v = par[i][v];
	if(u == v)return ans;
	for(int i=18;i>=0;i--){
		if(par[i][u] != par[i][v]){
			ans = max({ans, mx[i][u], mx[i][v]});
			u = par[i][u], v = par[i][v];
		}
	}
	return max({ans, mx[0][u], mx[0][v]});
}
inline int conv(int x, int y){
	return (x-1) * c + y;
}
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
void solve(){
	cin >> r >> c >> n >> q;
	for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)cin >> G[i][j], dist[i][j] = 1e9;
	queue<pii>qu;
	for(int i=1;i<=n;i++){
		int x,y;cin >> x >> y;
		root[i] = i;
		A[x][y] = i;
		haha[i] = {x, y};
		qu.push({i, {x, y}});
		dist[x][y] = 0;
	}
	while(!qu.empty()){
		int x = qu.front().fi, y = qu.front().se.fi, z = qu.front().se.se;
		qu.pop();
		for(int i=0;i<4;i++){
			int y1 = y + dx[i];
			int z1 = z + dy[i];
			if(y1 < 1 || y1 > r || z1 < 1 || z1 > c)continue;
			if(G[y1][z1] == '#')continue;
			if(dist[y1][z1] > dist[y][z] + 1)dist[y1][z1] = dist[y][z] + 1, A[y1][z1] = x, qu.push({x, {y1, z1}});
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(G[i][j] == '#')continue;
			int x = i ,y = j;
			for(int k=0;k<2;k++){
				int x1 = x + dx[k], y1 = y + dy[k];
				if(x1 < 1 || x1 > r || y1 < 1 || y1 > c)continue;
				if(G[x1][y1] == '#')continue;
				if(A[x][y] != A[x1][y1] && A[x][y] && A[x1][y1]){
					edges.push_back({dist[x][y] + dist[x1][y1] + 1, {A[x][y], A[x1][y1]}});
				}
			}
			
		}
	}
	/*
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++)cout << A[i][j] << " ";
		cout << '\n';
	}
	
	map<pi, int> :: iterator it;
	for(it = m.begin(); it != m.end(); it++){
		int x = it->first.fi, y = it->fi.se, z = it->se;
		edges.push_back({z, {x, y}});
		//cout << x << " " << y << " " << z << '\n';
	}
	*/
	sort(edges.begin(), edges.end());
	for(auto i: edges){
		int a = i.se.fi, b = i.se.se, w = i.fi;
		if(getr(a) == getr(b))continue;
		merge(a, b);
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
		//cout << a << " " << b << " " << w << '\n';
	}
	for(int i=1;i<=n;i++)if(!dep[i])dfs(i, -1, 1);
	for(int i=1;i<19;i++){
		for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]], mx[i][j] = max(mx[i-1][j], mx[i-1][par[i-1][j]]);
	}
	while(q--){
		int x,y;cin >> x >> y;
		if(getr(x) != getr(y))cout << -1 << '\n';
		else cout << lca(x, y) -1 << '\n';
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

bottle.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main(){
      | ^~~~

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