# 2019 USACO Open Silver Problem 3

I am working on this problem : http://www.usaco.org/index.php?page=viewproblem2&cpid=944

My code works on the first 6 test cases but it times out on the last 4. Can someone show me how to make this code more efficient?

Strategy: I am using a DFS to find all the cows in a group. And I store the cow numbers of all the cows in the group. Then I calculate the perimeter. Also, to make this more efficient I remove all the cows that I visited in the DFS because a DFS on the other cows in the same system would result in the exact same perimeter.

Code:
const int MN = 1e5 + 10;
bool visited[MN];
int N, M;
vector current;

void dfs(long node) {
visited[node] = true;
if (!visited[u]) {
current.push_back(u);
dfs(u);
}
}
}

int main() {
freopen(“fenceplan.in”, “r”, stdin);
freopen(“fenceplan.out”, “w”, stdout);
cin >> N >> M;
map<long, pair<long, long>> inputs;
for (int i = 0; i < N; i++) {
long x, y;
cin >> x >> y;
inputs.insert({i + 1, make_pair(x, y)});
}
for (int i = 0; i < M; i++) {
int cow1, cow2;
cin >> cow1 >> cow2;
}

``````vector<int> cows;
for (int i = 1; i <= N; i++) {
cows.push_back(i);
}
long ans = 1000000000000;
long x, y;
long minX = 100000000;
long miny = 1000000000;
long maxX = -1000000000;
long maxY = -1000000000;

while (cows.size() != 0) {

current.clear();
current.push_back(cows[0]);

dfs(cows[0]);

minX = 100000000;
miny = 1000000000;
maxX = -1000000000;
maxY = -1000000000;
for (int i = 0; i < current.size(); i++) {

cows.erase(std::remove(cows.begin(), cows.end(), current[i]), cows.end());
x = inputs[current[i]].first;
y = inputs[current[i]].second;
minX = min(x, minX);
miny = min(y, miny);
maxX = max(x, maxX);
maxY = max(y, maxY);

}

ans = min(ans, 2 * (maxX - minX) + 2 * (maxY - miny));
}
cout << ans;
return 0;
``````

}

how can I make this faster?

``````const int MN = 1e5 + 10;
bool visited[MN];
int N, M;
vector current;

void dfs(long node) {
visited[node] = true;
if (!visited[u]) {
current.push_back(u);
dfs(u);
}
}
}

int main() {
freopen("fenceplan.in", "r", stdin);
freopen("fenceplan.out", "w", stdout);
cin >> N >> M;
map<long, pair<long, long>> inputs;
for (int i = 0; i < N; i++) {
long x, y;
cin >> x >> y;
inputs.insert({i + 1, make_pair(x, y)});
}
for (int i = 0; i < M; i++) {
int cow1, cow2;
cin >> cow1 >> cow2;
}

vector<int> cows;
for (int i = 1; i <= N; i++) {
cows.push_back(i);
}
long ans = 1000000000000;
long x, y;
long minX = 100000000;
long miny = 1000000000;
long maxX = -1000000000;
long maxY = -1000000000;

while (cows.size() != 0) {

current.clear();
current.push_back(cows[0]);

dfs(cows[0]);

minX = 100000000;
miny = 1000000000;
maxX = -1000000000;
maxY = -1000000000;
for (int i = 0; i < current.size(); i++) {

cows.erase(std::remove(cows.begin(), cows.end(), current[i]), cows.end());
x = inputs[current[i]].first;
y = inputs[current[i]].second;
minX = min(x, minX);
miny = min(y, miny);
maxX = max(x, maxX);
maxY = max(y, maxY);

}

ans = min(ans, 2 * (maxX - minX) + 2 * (maxY - miny));
}
cout << ans;
return 0;
}
``````

FTFY.

Also, do you know the complexity of your solution? Why it’s TLE-ing shouldn’t be too hard to figure out.

Here is my solution for this problem…

``````#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;

vector<pi> cows(100000);
bool visited[100000];

int minX, minY, maxX, maxY;

void DFS(int node){
if(visited[node]){
return;
}
minX = min(cows[node].first, minX),
maxX = max(cows[node].first, maxX),
minY = min(cows[node].second, minY),
maxY = max(cows[node].second, maxY);
visited[node] = true;
DFS(connected);
}
}

int main(){
freopen("fenceplan.in", "r", stdin);
freopen("fenceplan.out", "w", stdout);
int n, m; cin >> n >> m;
for(int i=0; i<n; i++){
cin >> cows[i].first >> cows[i].second;
}
for(int i=0; i<m; i++){
int a, b; cin >> a >> b;
--a, --b;
}
int perimeter = 400000000;
for(int i=0; i<n; i++){
if(!visited[i]){
minX = cows[i].first,
maxX = cows[i].first,
minY = cows[i].second,
maxY = cows[i].second;
DFS(i);
perimeter = min(perimeter, 2 * (maxX - minX) + 2 * (maxY - minY));
}
}
cout << perimeter << endl;
}
``````

The reason you get TLE is that the solution should be O(N + M). However, you made it an O(N^2 + M) solution, which doesn’t satisfy the problem constraints…

You should rethink your logic. Also, make sure to reformat your code…

You should just run a DFS for each node if not visited. Find the minx, maxx, miny, miny. This will create a box and then your done.

Which is exactly the logic of my code…

The logic u provided could be wrong. What if (maxx - minx) is at its minimum but (maxy - miny) is super large. That won’t work. Instead, you should compute the maximum perimeter, rather than finding each individual component…

No, my logic was simplified greatly, but I can put my code if u want. Its correct.

It should be the minx, maxx, miny, maxy of the current connected component, though.

Yeah that’s what I put in my code. Sorry if I didn’t specify in this chat.