USACO 2019 US Open Contest, Silver Problem 3

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!!

Since the coordinates can go up to 10^8, the maximum possible perimeter is 4 * 10^8. Your ans is set to 999999, so raise it to 10^9. The miny has the same problem, it is now at 10^7, so change that as well.

OMG that was the issue. Thanks so much. I guess we can consider this integer underflow.

Next time you should try downloading the test data …

Yeah I did that, but I was oblivious to what was causing the problem. :confused: