Submission #156103

#	Time	Username	Problem	Language	Result	Execution time	Memory
156103		shuvi_dola	물병 (JOI14_bottle)	C++14	0 / 100	497 ms	44116 KiB

bottle

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int P = 2e5 + 5;
const int Tx[] = {-1, 0, 1, 0};
const int Ty[] = {0, 1, 0, -1};
typedef pair <int,int> pi;
char a[N][N];
int dist[N][N], id[N][N];
queue <pi> q;
vector <pair <int, pi> > edge;
int dep[P], up[P][25], anc[P][25];
int link[P], size[N];
vector <pi> g[P];
int H, W, p, que;
bool vis[P];
void dfs(int u, int p)
{
	vis[u] = 1;
	for(int i = 1; i <= 20; i++)
	{
		anc[u][i] = anc[anc[u][i - 1]][i - 1];
		up[u][i] = max(up[u][i - 1], up[anc[u][i - 1]][i - 1]);
	}
	for(auto x : g[u])
	{
		int v = x.first, w = x.second;
		if(v == p)
			continue;
		dep[v] = dep[u] + 1, 
		anc[v][0] = u, up[v][0] = w;
		dfs(v, u);
	}
}

void init()
{ for(int i=1;i<=p;i++) link[i] = i; for(int i=1;i<=p;i++) size[i] = 1; }
int find(int x)
{ while(x != link[x]) x = link[x]; return x; }
bool same(int a,int b)
{ return find(a) == find(b); }
void unite(int a,int b)
{ a = find(a); b = find(b); if(size[a] < size[b]) swap(a,b); size[a] += size[b]; link[b] = a; }
bool ck(int x, int y)
{ return (x >= 1 && y >= 1 && x <= H && y <= W && a[x][y] == '.'); }

int max_path(int u, int v)
{
    if (!same(u, v)) return -1;
    int ans = 0;
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; --i) if (dep[u] - (1 << i) >= dep[v]) ans = max(ans, up[u][i]), u = anc[u][i];
    if (u == v) return ans;
    for (int i = 20; i >= 0; --i) if (anc[u][i] != anc[v][i]) ans = max(ans, max(up[u][i], up[v][i])), u = anc[u][i], v = anc[v][i];
    return max(ans, max(up[u][0], up[v][0]));
}

void bfs()
{
	while(q.size() > 0)
	{
		int x = q.front().first,
			y = q.front().second;
		// cout << x << ' ' << y << '\n';
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int nx = x + Tx[i], ny = y + Ty[i];
			if(ck(nx, ny) == 1 && dist[nx][ny] == -1)
			{
				dist[nx][ny] = dist[x][y] + 1, 
				id[nx][ny] = id[x][y];
				q.push({nx, ny});
			}
			if(ck(nx, ny) && dist[nx][ny] != -1)
			{
				int a = id[nx][ny], b = id[x][y];
				if(a != b)
				{
					// cout << a << ' ' << b << endl;
					edge.push_back({dist[nx][ny] + dist[x][y], {a, b}});
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> H >> W >> p >> que;
	init();
	for(int i = 1; i <= H; i++)
	{
		for(int j = 1; j <= W; j++)
		{
			dist[i][j] = -1;
			id[i][j] = 0;
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= p; i++)
	{
		int x, y; cin >> x >> y;
		// cout << x << y << endl;
		dist[x][y] = 0;
		id[x][y] = i;
		q.push({x, y});
	}
	bfs();
	sort(edge.begin(), edge.begin());
	for(auto e : edge)
	{
		int x = e.second.first, 
			y = e.second.second;
		if(!same(x, y))
		{
			// cout << x << ' ' << y << '\n';
			g[x].push_back({y, e.first});
			g[y].push_back({x, e.first});
			unite(x, y);
		}
	}
	for(int i = 1; i <= p; i++)
	{
		if(vis[i] == 0)
			dfs(i, i);
	}	
	while(que--)
	{
		int s, t;
		cin >> s >> t;
		cout << max_path(s, t) << '\n';
	}
}

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