Submission #156099

#	Time	Username	Problem	Language	Result	Execution time	Memory
156099		puppies_and_rainbows	물병 (JOI14_bottle)	C++14	70 / 100	5097 ms	242996 KiB

bottle

#include <bits/stdc++.h>
#define union khoaphamdangyeuhihixd
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[200005];
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]==0)
	{
		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],{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});
		}
	}
}

bool visited[200005];

void dfs(int node, int fa)
{
	visited[node]=1;
	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].first;
	}
	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();
	for(int i=1; i<=p; i++)
	{
		if(!visited[i])
		{
			dfs(i, i);
		}
	}
	// 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<<find(u)<<" "<<find(v)<<endl;
		if(find(u)==find(v)) cout<<lca(u, v)<<endl;
		else cout<<-1<<endl;
	}
}

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