Multiplayer Moo https://usaco.guide/silver/ff?lang=cpp
I don’t understand where my code is timing out.
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <fstream>
using namespace std;
int n;
int id[251][251];
bool visited[251][251];
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};
vector <vector <pair<int, int>>> conComp;
vector <pair<int, int>> temp;
vector <int> temp2;
vector <vector <int>> adj;
vector <int> id_Comp;
bool visited2[251];
vector <int> temp3;
void dfs(int row, int col, int numb) {
for (int k = 0; k < 4; k++) {
int r = row + di[k];
int c = col + dj[k];
if ((r >= 0) && (r < 251) && (c >= 0) && (c < 251)) {
if ((!visited[r][c]) && (id[r][c] == numb)) {
visited[r][c] = true;
temp.push_back({r, c});
dfs(r, c, numb);
}
}
}
}
void dfs2(int node, int num1, int num2) {
for (int g = 0; g < adj[node].size(); g++) {
if (!visited2[adj[node][g]]) {
if ((id_Comp[adj[node][g]] == num1) || (id_Comp[adj[node][g]] == num2)) {
visited2[adj[node][g]] = true;
temp3.push_back(adj[node][g]);
dfs2(adj[node][g], num1, num2);
}
}
}
}
int main()
{
ifstream fin ("multimoo.in");
ofstream fout ("multimoo.out");
//cin >> n;
fin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//cin >> id[i][j];
fin >> id[i][j];
}
}
for (int i = 0; i < 251; i++) {
for (int j = 0; j < 251; j++) {
visited[i][j] = false;
}
}
int ans1 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
visited[i][j] = true;
temp.push_back({i, j});
dfs(i, j, id[i][j]);
conComp.push_back(temp);
int sum1 = temp.size();
ans1 = max(ans1, sum1);
temp.clear();
}
}
}
//cout << ans1 << endl;
fout << ans1 << endl;
for (int k = 0; k < conComp.size(); k++) {
set <int> neighbours;
for (int l = 0; l < conComp[k].size(); l++) {
for (int a = 0; a < 4; a++) {
int r = conComp[k][l].first + di[a];
int c = conComp[k][l].second + dj[a];
if ((r >= 0) && (r < 251) && (c >= 0) && (c < 251)) {
if (id[conComp[k][l].first][conComp[k][l].second] != id[r][c]) {
bool isFound = false;
for (int f = 0; f < conComp.size(); f++) {
if (f == k) {
continue;
}
for (int g = 0; g < conComp[f].size(); g++) {
if ((conComp[f][g].first == r) && (conComp[f][g].second == c)) {
neighbours.insert(f);
isFound = true;
break;
}
}
if (isFound) {
break;
}
}
}
}
}
}
for (auto el: neighbours) {
temp2.push_back(el);
}
adj.push_back(temp2);
temp2.clear();
}
for (int k = 0; k < conComp.size(); k++) {
id_Comp.push_back(id[conComp[k][0].first][conComp[k][0].second]);
}
int ans2 = 0;
for (int a = 0; a < id_Comp.size(); a++) {
for (int b = 0; b < id_Comp.size(); b++) {
if (a == b) {
continue;
}
if (id_Comp[a] == id_Comp[b]) {
continue;
}
for (int i = 0; i <= conComp.size(); i++) {
visited2[i] = false;
}
for (int i = 0; i < conComp.size(); i++) {
if (!visited2[i]) {
if ((id_Comp[i] == id_Comp[a]) || (id_Comp[i] == id_Comp[b])) {
visited2[i] = true;
temp3.push_back(i);
dfs2(i, id_Comp[a], id_Comp[b]);
int sum = 0;
for (int x = 0; x < temp3.size(); x++) {
sum += (conComp[temp3[x]].size());
}
//ans2 = max(ans2, sum);
if (ans2 < sum) {
ans2 = sum;
}
temp3.clear();
}
}
}
}
}
//cout << ans2 << endl;
fout << ans2 << endl;
}