Hi,
I’m working on the USACO problem connecting two barns, usaco.guide link here. My code is
#include<iostream>
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
int T,N,M,A[100001];// A is the array such that A[i] gives the index of the connected component that field i is in
vector<int>L[100001];// L is the adjacency list
vector<ll>S[100001];// S is an array of vectors such that S[i] stores all the fields in connected component i
ll md(int i,int j)// basic two-pointers algorithm to find the minimum possible value of abs(S[i][p]-S[j][q])
{
ull p,q;
ll ans;
p=0;// p,q pointers
q=0;
ans=100000;
while ((p<S[i].size())&&(q<S[j].size()))
{
ans=min(ans,abs(S[i][p]-S[j][q]));
if (S[i][p]<S[j][q])// whichever side is smaller steps ahead by 1
{
p+=1;
}
else
{
q+=1;
}
}
return ans;
}
void go(int i)// simple dfs to find fields in the same component as i
{
for (auto j : L[i])
{
if (A[j]==0)
{
A[j]=A[i];
go(j);
}
}
return;
}
void solve()// solve() function for 1 independent test case
{
int i,j,k,ctr;
ll ans;
for (i=0;i<=N-1;i=i+1)// reset everything
{
A[i]=0;
L[i].clear();
S[i].clear();
}
cin>>N>>M;
for (i=0;i<=M-1;i=i+1)// build adjacency list
{
cin>>j>>k;
L[j-1].push_back(k-1);
L[k-1].push_back(j-1);
}
ctr=0;// counts number of connected components
for (i=0;i<=N-1;i=i+1)// begin dfs
{
if (A[i]==0)// if i isn't in any previously identified component (A[i]=0 by default), mark it and run dfs
{
ctr+=1;
A[i]=ctr;
go(i);
}
}
for (i=0;i<=N-1;i=i+1)// build S
{
S[A[i]-1].push_back(i);
}
ans=md(A[0]-1,A[N-1]-1)*md(A[0]-1,A[N-1]-1);// running 2P algorithms
for (i=0;i<=ctr-1;i=i+1)
{
ans=min(ans,md(A[0]-1,i)*md(A[0]-1,i)+md(i,A[N-1]-1)*md(i,A[N-1]-1));
}
cout<<ans<<endl;
}
int main()
{
int i;
cin>>T;
for (i=0;i<=T-1;i=i+1)
{
solve();
}
return 0;
}
However, this gives TLE on the final 5 test cases. I’ve tried to use binary search instead of 2P for the md() function, but it was even slower. It seems like the md() function is the part the uses the most time, but I don’t know how to fix this. Any help will be appreciated. thanks.