can anyone tell why my second code gives tle, while first gets accepted?? Problem link : https://codeforces.net/contest/2004/problem/D
coorect code : ~~~~~
include <bits/stdc++.h>
using namespace std;
string colors[] = {"BG", "BR", "BY", "GR", "GY", "RY"};
bool hasCommmon(string &a, string &b) { if (a[0] == b[0] || a[1] == b[0] || a[0] == b[1] || a[1] == b[1]) return 1; else return 0; }
void solve() { int n, q; cin >> n >> q;
unordered_map<string, vector<int>> mp; vector<string> city(n + 1); for (int i = 0; i < n; i++) { string s; cin >> s; mp[s].push_back(i + 1); city[i + 1] = s; } for (int i = 0; i < 6; i++) { auto &v = mp[colors[i]]; sort(v.begin(), v.end()); } while (q--) { int x, y; cin >> x >> y; if (x > y) swap(x, y); string s1 = city[x]; string s2 = city[y]; if (hasCommmon(s1, s2)) { cout << abs(x - y) << "\n"; } else { int ans = 1e9; for (int i = 0; i < 6; i++) { if (colors[i] == s1 || colors[i] == s2) continue; auto &v = mp[colors[i]]; auto it = lower_bound(v.begin(), v.end(), x); if (it != v.end()) { ans = min(ans, abs(x - *it) + abs(*it - y)); } if (it != v.begin()) { it--; ans = min(ans, abs(x - *it) + abs(*it - y)); } } cout << ((ans == 1e9) ? -1 : ans) << "\n"; } }
}
signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) solve(); exit(0); } ~~~~~
TLE Code : ~~~~~
include <bits/stdc++.h>
using namespace std;
define endl '\n'
using ll = long long;
define pb push_back
define popb pop_back
define lb lower_bound
define ub upper_bound
define int long long
int intersect(string a, string b) { if (a[0] == b[0] || a[0] == b[1] || a[1] == b[0] || a[1] == b[1]) return 1; else return 0; }
void solve() { int n, q; cin >> n >> q; unordered_map<string, vector> mp; vector col(n + 1); for (int i = 0; i < n; i++) { string s; cin >> s; mp[s].pb(i); col[i] = s; } for (auto it : mp) sort(it.second.begin(), it.second.end()); // cout<<"MAP SIZE: "<<mp.size()<<endl; while (q--) { int x, y; cin >> x >> y; if (x > y) swap(x, y);
x--; y--; string a, b; // for(auto it:mp){ // if(it.second.find(x)!=it.second.end()){ // a = it.first; // break; // } // } // for(auto it:mp){ // if(it.second.find(y)!=it.second.end()){ // b = it.first; // break; // } // } a = col[x]; b = col[y]; if (intersect(a, b)) { cout << abs(x - y) << endl; continue; } int ans = 1e9; for (auto it : mp) { if (it.first == a || it.first == b) continue; auto pos = lower_bound(it.second.begin(), it.second.end(), x); if (pos != it.second.end()) ans = min(ans, abs(*pos - x) + abs(*pos - y)); if (pos != it.second.begin()) { pos--; ans = min(ans, abs(*pos - x) + abs(*pos - y)); } } if (ans == 1e9) cout << -1 << endl; else cout << ans << endl; }
}
signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt; cin >> tt; while (tt--) solve(); }
~~~~~