oj.uz

Submission #676460

# Submission time Handle Problem Language Result Execution time Memory
676460 2022-12-31T03:25:41 Z penguin133 물병 (JOI14_bottle) C++17
100 / 100
 1222 ms 195700 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10964 KB Output is correct
2 Correct 9 ms 12432 KB Output is correct
3 Correct 10 ms 12884 KB Output is correct
4 Correct 61 ms 14788 KB Output is correct
5 Correct 61 ms 14872 KB Output is correct
6 Correct 59 ms 14668 KB Output is correct
7 Correct 59 ms 14684 KB Output is correct
8 Correct 69 ms 15064 KB Output is correct
9 Correct 62 ms 14836 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 34096 KB Output is correct
2 Correct 39 ms 20224 KB Output is correct
3 Correct 361 ms 83584 KB Output is correct
4 Correct 441 ms 86608 KB Output is correct
5 Correct 483 ms 89976 KB Output is correct
6 Correct 346 ms 83628 KB Output is correct
7 Correct 443 ms 86916 KB Output is correct
8 Correct 474 ms 89956 KB Output is correct
9 Correct 508 ms 97052 KB Output is correct
10 Correct 390 ms 82828 KB Output is correct
11 Correct 419 ms 84960 KB Output is correct
12 Correct 163 ms 75564 KB Output is correct
13 Correct 225 ms 72920 KB Output is correct
14 Correct 154 ms 75660 KB Output is correct
15 Correct 194 ms 72960 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 34184 KB Output is correct
2 Correct 37 ms 18160 KB Output is correct
3 Correct 299 ms 81136 KB Output is correct
4 Correct 444 ms 86724 KB Output is correct
5 Correct 475 ms 89776 KB Output is correct
6 Correct 635 ms 96020 KB Output is correct
7 Correct 383 ms 82700 KB Output is correct
8 Correct 440 ms 87024 KB Output is correct
9 Correct 171 ms 75408 KB Output is correct
10 Correct 204 ms 73164 KB Output is correct
11 Correct 182 ms 71516 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 88596 KB Output is correct
2 Correct 878 ms 170768 KB Output is correct
3 Correct 427 ms 82816 KB Output is correct
4 Correct 1098 ms 180284 KB Output is correct
5 Correct 1222 ms 195700 KB Output is correct
6 Correct 581 ms 98956 KB Output is correct
7 Correct 398 ms 82636 KB Output is correct
8 Correct 132 ms 71424 KB Output is correct
9 Correct 1083 ms 194112 KB Output is correct
10 Correct 757 ms 167412 KB Output is correct
11 Correct 1090 ms 193592 KB Output is correct
12 Correct 923 ms 179216 KB Output is correct