Submission #156094

#	Time	Username	Problem	Language	Result	Execution time	Memory
156094		puppies_and_rainbows	물병 (JOI14_bottle)	C++14	0 / 100	1960 ms	141096 KiB

bottle

#include <bits/stdc++.h>
#define union doradangyeu
using namespace std;

int h1, w, p, q;

int last[2005][2005], dist[2005][2005];
queue<pair<int, int> > b;
string s[2005];
vector<pair<int, int> > adj[100005];
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
vector<pair<int, pair<int, int> > > edges;
int f[200005], h[200005];
pair<int, int>  anc[200005][20];

int find(int i)
{
	return f[i]==i? f[i]:find(f[i]);
}

void union(int i, int j)
{
	f[find(i)]=find(j);
}

bool check(int a, int b)
{
	if(a>0&&b>0&&a<=h1&&b<=w&&s[a][b]!='#'&&!last[a][b])
	{
		return true;
	}
	return false;
}

void bfs()
{
	while(b.size())
	{
		pair<int, int> fr=b.front();
		b.pop();
		for(int i=0; i<4; i++)
		{
			int ax=fr.first+dx[i], ay=fr.second+dy[i], ck=check(ax, ay);
			if(ck)
			{
				last[ax][ay]=last[fr.first][fr.second];
				dist[ax][ay]=dist[fr.first][fr.second]+1;
				b.push({ax, ay});
			}
			else if(last[ax][ay]!=0)
			{
			 	edges.push_back({dist[ax][ay]+dist[fr.first][fr.second]+1,{last[ax][ay], last[fr.first][fr.second]}});
			}
		}	
	}
}

void kruskal()
{
	sort(edges.begin(), edges.end());
	for(auto i:edges)
	{
		if(find(i.second.second)!=find(i.second.first))
		{
			union(i.second.first, i.second.second);
			adj[i.second.first].push_back({i.second.second, i.first});
			adj[i.second.second].push_back({i.second.first, i.first});
		}
	}
}

void dfs(int node, int fa)
{
	h[node]=h[fa]+1;
	anc[node][0].first=fa;
	for(int i=1; i<=19; i++)
	{
		anc[node][i].first=anc[anc[node][i-1].first][i-1].first;
		anc[node][i].second=max(anc[node][i-1].second, anc[anc[node][i-1].first][i-1].second);
	}
	for(auto i:adj[node])
	{
		if(i.first==fa)
		{
		 	continue;
		}
		anc[i.first][0].second=i.second;
		dfs(i.first, node);
	}
}

int lca(int u, int v)
{
	// cout<<u<<" "<<v<<endl;
	int lel=0;
	if(h[u]<h[v])
	{
		swap(u, v);
	}
	for(int i=18; i>=0; i--)
	{
		if(h[anc[u][i].first]<h[v]) continue;
		lel=max(lel, anc[u][i].second);
		u=anc[u][i].first;
	}
	// cout<<u<<endl;
	if(u==v) return lel;
	for(int i=18; i>=0; i--)
	{
		if(anc[u][i].first==anc[v][i].first) continue;
		lel=max(lel, max(anc[u][i].second, anc[v][i].second));
		u=anc[u][i].first;
		v=anc[v][i].second;
	}
	return max(lel, max(anc[u][0].second, anc[v][0].second));
}

signed main()
{
	cin>>h1>>w>>p>>q;
	for(int i=1; i<=p; i++)
	{
		f[i]=i;
	}
	for(int i=1; i<=h1; i++)
	{
		cin>>s[i];
		s[i]='!'+s[i]+'!';
	}
	for(int i=1; i<=p; i++)
	{
		int u, v;
		cin>>u>>v;
		b.push({u, v});
		last[u][v]=i;
	}
	bfs();
	kruskal();
	dfs(1, 1);
	// for(int i=1; i<=h1; i++)
	// {
	// 	for(int j=1; j<=w; j++)
	// 	{
	// 		cout<<last[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	for(int i=1; i<=q; i++)
	{
		int u, v;
		cin>>u>>v;
		cout<<lca(u, v)-1<<endl;
	}
}

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