So I was solving this problem and the answer was coming up wrong for all of the test cases except the first. I tried looking through and finding any mistakes, but I couldn’t find any.
Here is my code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const int mxn=2E5;
int n,m, moo[mxn+1];
vector<int> adj[mxn+1];
pair<int,int> coord[mxn+1];
void dfs(int node, int l){
moo[node]=l;
for(int i: adj[node])
if(!moo[i])
dfs(i,l);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
freopen("fenceplan.in","r", stdin);
freopen("fenceplan.out","w", stdout);
cin >> n >>m;
for(int i=1,a,b;i<=n;i++){ //assign each cow to a moo network
cin>>a>>b;
coord[i]={a,b};
}
for(int i=0,a,b;i<m;i++){
cin >> a >>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int label=1;
for(int i=1;i<=n;i++) //the actual assigning
if(!moo[i])
dfs(i,label++);
vector<int> network[label]; //store each cow network into a vector
for(int i=1;i<=n;i++)
network[moo[i]].push_back(i);
ll ans=999999;
for(int i=1;i<label;i++){
ll minx=99999999,miny=9999999,maxx=0,maxy=0;
for(int j:network[i]){
//create the minimum size box to store all of the cows in each moo network
minx=min((ll)coord[j].f,minx);
miny=min((ll)coord[j].s,miny);
maxx=max((ll)coord[j].f,maxx);
maxy=max((ll)coord[j].s,maxy);
}
int temp=0;
if(maxx==minx) temp+=2;
if(maxy==miny) temp+=2;
ans = min(2*(maxy-miny)+2*(maxx-minx)+temp,ans); //find the least size perimeter
}
cout << ans << "\n";
}
I am hoping that someone can find a fault in the logic so that I can solve this problem. Thanks!!
