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!