# Bronze 2019 US Open Milk Factory - Fails 9th test case

Hi,
I have a partial solution to 2019 Bronze US Open Problem 2. It only fails the 9th test case. What is wrong with my code?
Link to question: USACO

# Code:

#include <bits/stdc++.h>
using namespace std;
//Recursive method, moves through graph, similar to dfs
void visit(vector<int>& paths,vector<vector<bool>>& visited,vector<bool>& temp,map<int,vector<int>>& p){
for(auto x:paths){
temp[x-1] = true;
if(p.count(x)){
visit(p[x],visited,temp,p);
}
}
}
int main(){
ifstream fin("factory.in");
ofstream fout("factory.out");
int n,a,b;
map<int,vector<int>> paths; // Graph
bool found = false;
fin>>n;
for(int i = 0; i<n; i++){
fin>>a>>b;
paths[a].push_back(b); // Build graph
}
vector<vector<bool>> visited;
vector<bool> temp(n);

for(auto p : paths){ // Travels through graph. If a node can be reached, corresponding element in temp is marked true. A different vector is used for different starting stations
fill(temp.begin(),temp.end(),false);
temp[p.first-1] = true;
visit(p.second,visited,temp,paths);
visited.push_back(temp);
}
temp = visited[0];
for(auto t:visited){ // Looks for intersection of trues among all the vectors in visited. An intersection means that node can be visited from all other stations
for(int k = 0; k<n; k++){
if(!(temp[k]&&t[k])) temp[k] = false;
}
}

for(int j = 0; j<n; j++){ // Outputs first intersection (min)
if(temp[j]) {
fout<<j+1<<"\n";
found = true;
break;
}
}
if(!found) fout<<"-1\n";

}


# 9.in:

100
78 51
85 35
58 57
52 93
64 94
23 79
93 53
79 95
65 89
28 85
60 18
56 79
41 5
34 98
51 81
46 29
1 78
43 70
19 13
36 61
10 6
7 14
83 18
32 79
6 18
70 33
24 61
3 1
80 7
90 43
9 49
57 56
55 7
89 19
27 57
26 18
13 28
25 77
62 40
41 90
22 40
35 80
54 4
39 55
30 9
59 71
15 25
87 81
81 56
75 69
94 18
71 67
50 6
47 81
99 94
91 22
69 37
49 68
4 45
12 79
17 57
100 54
96 40
66 82
86 46
68 86
92 95
76 56
44 18
88 86
33 15
95 38
84 12
42 45
63 64
37 9
29 48
11 81
8 63
53 75
98 89
20 8
18 4
73 45
72 45
61 45
21 52
77 66
82 59
16 49
97 94
14 3
67 52
31 74
2 98
38 74
74 20
48 98
40 63


Correct output: -1
My wrong output: 45

Thanks in advance!

Maybe 1) Put the problem link (even though I myself know this problem, plenty of other people don’t!) and 2) Edit your code to have some syntax highlighting and some better comments.

Hi anon, it seems like you are trying to solve this problem using DFS. I’m not really sure what the problem is, but I would recommend you download the test data. If the 9th test case is too big, then I would recommend you read my solution here: DFS Milk Factory Solution. I think you’re overcomplicating this a bit, so check my solution out for a simplified version. Best of luck!

Suggested changes made. Thanks for your suggestions!

Hi,
I skimmed through the solution and it seems that I may have misread the question a bit. I thought I would need to find a station that can be accessed from all other stations, but the solution indicates that I would need to find a station that can access all other stations. Is this correct? Thanks for your help!

Yeah, I think that’s what you misread. Good job on figuring out your mistake.

(obligatory repost) \quad

I mean, I think they already figured out their problem…

Yeah, but in any case you should follow the directions in the linked post before posting.