# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
863878 | 2023-10-21T10:06:55 Z | prairie2022 | Railway Trip 2 (JOI22_ho_t4) | C++17 | 0 ms | 0 KB |
for(cin >> q; q; q--){ cin >> s >> t; vector<vector<int>> way(n+1); for(int i=0; i<m; i++){ if(near(s, rail[i])) way[near(s, rail[i])].push_back(i); } vector<int> dp(n+1, -1); dp[s] = 0; int l = s, r = s; queue<int> qu; for(qu.push(s); !qu.empty() || qu.front()==t; qu.pop()){ //cout << qu.front() << " : "; for(const int &w: way[qu.front()]){ //cout << w << ' '; if(rail[w].S>r){ for(int i=r+1; i<=rail[w].S; i++){ dp[i] = dp[qu.front()]+1; qu.push(i); } r = rail[w].S; } else if(rail[w].S<l){ for(int i=l-1; i>=rail[w].S; i--){ dp[i] = dp[qu.front()]+1; qu.push(i); } l = rail[w].S; } } //cout << '\n'; } cout << dp[t] << '\n'; } return 0; }