1804F - Approximate Diameter - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int n,m,Q;
vector<int> e[100010],ti[100010];
int ans[100010],dis[100010];
int bbd[100010];
queue<int> q;
int solve(int lim)
{
	if(bbd[lim])
		return bbd[lim];
	for(int i=2;i<=n;i++)
		dis[i]=1e9;
	q.push(1);
	int ans=0;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		ans=max(ans,dis[x]);
		for(int i=0;i<e[x].size();i++)
			if(ti[x][i]<=lim&&dis[e[x][i]]>dis[x]+1)
			{
				dis[e[x][i]]=dis[x]+1;
				q.push(e[x][i]);
			}
	}
	return bbd[lim]=ans;	
}
int main()
{
	scanf("%d%d%d",&n,&m,&Q);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		ti[x].push_back(0);
		e[y].push_back(x);
		ti[y].push_back(0);
	}
	for(int i=1;i<=Q;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		ti[x].push_back(i);
		e[y].push_back(x);
		ti[y].push_back(i);
	}
	int lst=1;
	int cur=0;
	printf("%d ",cur=solve(0));
	while(lst<=Q)
	{
		int l=lst,r=Q,res=lst;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(solve(mid)>=(cur+1)/2)
				res=mid,l=mid+1;
			else
				r=mid-1;
		}
		for(int i=lst;i<=res;i++)
			ans[i]=cur;
		lst=res+1;
		cur=solve(res+1);
	}
	for(int i=1;i<=Q;i++)
		printf("%d ",ans[i]);
}