Checklist
Make sure to read all of How to ask for help on a problem before asking for help.
Problem Info
Fenced In - USACO
Question
My code is not working on 3 test cases and I don’t know why!
What I’ve Tried
I tried to find test cases to download but I haven’t found them.
My Work
#include <bits/stdc++.h>
using namespace std;
#define MAXM 4500000
#define MAXN 2010`Preformatted text`
long long a,b,n,m;
long long niz1[MAXN];
long long niz2[MAXN];
long long parent[MAXM];
long long siz[MAXM];
vector<pair<long long,pair<long long,long long>>> adj;
long long get(long long node)
{
if (node==parent[node]) return node;
else return get(parent[node]);
}
bool unite(long long node1,long long node2)
{
node1=get(node1);node2=get(node2);
if (node1==node2) return false;
if (siz[node1]<siz[node2]) swap(node1,node2);
parent[node2]=node1;
siz[node1]+=siz[node2];
return true;
}
int main()
{
freopen("fencedin.in", "r", stdin);
freopen("fencedin.out", "w", stdout);
for (long long i=0;i<MAXM;i++) parent[i]=i;
for (long long i=0;i<MAXM;i++) siz[i]=1;
cin>>a>>b>>n>>m;
for (long long i=1;i<=n;i++) cin>>niz1[i];
for (long long i=1;i<=m;i++) cin>>niz2[i];
niz1[0]=0;niz1[n+1]=a;niz2[0]=0;niz2[m+1]=b;
sort(niz1+1,niz1+n+1);sort(niz2+1,niz2+m+1);
for (long long i=1;i<=n+1;i++)
{
for (long long j=1;j<=m+1;j++)
{
if (i==n+1 and j==m+1) break;
else if (i==n+1)
{
long long val=niz1[i]-niz1[i-1];
long long node1=n*(m+1)+j;
long long node2=node1+1;
adj.push_back({val,{node1,node2}});
}
else if (j==m+1)
{
long long val=niz2[j]-niz2[j-1];
long long node1=i*(m+1);
long long node2=(i+1)*(m+1);
adj.push_back({val,{node1,node2}});
}
else
{
long long val1=niz1[i]-niz1[i-1];
long long node11=(i-1)*(m+1)+j;
long long node21=node11+1;
adj.push_back({val1,{node11,node21}});
long long val2=niz2[j]-niz2[j-1];
long long node12=(i-1)*(m+1)+j;
long long node22=node12+(m+1);
adj.push_back({val2,{node12,node22}});
}
}
}
sort(adj.begin(),adj.end());
long long ans=0;
for (long long i=0;i<adj.size();i++)
{
long long node1=adj[i].second.first;
long long node2=adj[i].second.second;
long long val=adj[i].first;
if (unite(node1,node2)) ans+=val;
}
cout<<ans<<endl;
}
So, in my code, I am making adj list of nodes and then I am running Kruskal’s MST(nothing special xd).